Доказательство. Необходимость. ( ) Пусть G=(V, U)-дерево

Необходимость. () Пусть G =(V, U) - дерево. Покажем, что |V| = |U| + 1. Рассмотрим некоторое корневое представление G.

К этому графу, пока это возможно, применяется следующее преобразование: выбирается произвольная висячая вершина и удаляется из графа вместе с ведущим в эту вершину ребром.

Очевидно, что через конечное число выполнений приведенного преобразования от графа G останется только корневая вершина.

Поскольку число удаленных при этом вершин равно числу удаленных ребер и одна вершина графа G осталась, то |V| = |U| + 1.

Достаточность. () Пусть G =(V, U) - неориентированный связный граф без петель, для которого
|V| = |U| + 1. Покажем, что G - это дерево.

Предположим противное: G не является деревом. Следовательно, в G имеются циклические ребра.

Выполним процедуру последовательного размыкания циклов в G,не нарушающего связности этого графа. Она основана на следующем элементарном действии: выбирается произвольный элементпрный цикл в G, длина которого не меньше чем 3,после чего из G удаляется любое ребро этого цикла.

Указанное действие повторяется до тех пор, пока в получаемых связных графах имеются циклические ребра.

Заданное преобразование графа заканчивается за конечное время и полученный в результате граф является связным.

Обозначим этот граф как G ^* = (V, U ^*). Поскольку G ^* не содержит циклических ребер, то он является деревом.

Поэтому из доказательства необходимости следует справедливость равенства: |V| = |U ^* | + 1.

Последнее противоречит начальному предположению о том, что |V| = |U| + 1, поскольку по построению графа G ^* должно выполняться неравенство: |U ^* | < |U|.

Полученное противоречие означает, что G не может содержать циклических ребер и является деревом.