Дерево, эквивалентные определения

Определение:

Ациклический граф - граф, в котором нет циклов.

Определение:

Дерево - это связный ациклический граф.

Определение:

Граф, не содержащий циклов, называется лесом.

Теорема:

Для графа [math]G[/math] следующие утверждения эквивалентны: 1) [math]G[/math] - дерево; 2) любые две вершины в [math]G[/math]соединены единственной простой цепью; 3) [math]G[/math] связный граф и [math]p = q + 1[/math]; 4) [math]G[/math] ациклический граф и [math]p = q + 1[/math]; 5) [math]G[/math] - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе [math]G + x[/math] будет точно один простой цикл; 6) G - связный граф, отличный от Kp для p [math]\ge[/math] 3, и если любую пару несмежных вершин соеденить ребром х, то в графе G + x будет точно один простой цикл; 7) G - Граф, отличный от K3 [math]\cup[/math] K1 и K3[math]\cup[/math] K2, p = q + 1, и если любую пару несмежных вершин соединить ребром x, то в графе G + x будет точно один простой цикл.

Следствие

В любом нетривиальном дереве имеется по крайней мере две висячие вершины.