Построить для дерево для графа с рёбрами E={(1,2),...

Можно построить остовное дерево (спаннинг-три) на вершинах $V=\{1,2,3,4,5,6\}$, выбрав 5 рёбер из $E$ так, чтобы граф остался связным и без циклов.

Один из вариантов:

$$T=\{(1,2),(1,4),(2,3),(2,5),(4,6)\}.$$

Все эти рёбра есть в $E$, дерево содержит $6$ вершин и $5$ рёбер, циклов нет, связность есть.

В виде структуры (корень 1):

• $1$: дети $2,4$
• $2$: дети $3,5$
• $4$: ребёнок $6$

ASCII-вид:

text
1
├─2
│ ├─3
│ └─5
└─4
  └─6