Деревом называется конечный связный граф без
циклов. Лесом из k деревьев
называется граф без циклов, у которого число связности равно k, k>1.
Теорема.
Для конечного графа {M, N, T) следующие 3 утверждения эквивалентны:
1)
(M, N, T) – дерево, т. е.
связный граф без циклов.
2)
(M, N, T) не содержит
циклов и |N|=|M|-1.
3) (M, N, T) связен
и |N|=|M|-1.