Деревья и остовные деревья

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

Предположим, что цикл не содержит вершин и Тогда в нем есть либо вершина, все ребра которой в — это ее ребра в цикле и тогда удаление любого из ребер, инцидентных ей, приводит к тому, что получается новое дерево в котором есть дополнительная висячая вершина, удаление которой сохраняет связность либо в этом графе такой вершины нет, что означает, что уже в дереве содержалось хотя бы три висячих вершины, каждую из которых можно удалять.

Предположим теперь, что содержит одну из вершин или (без ограничения общности можно полагать, что это вершина Тогда можно из цикла удалить любое ребро, не инцидентное с сохранением связности. Тогда получится новое дерево в котором не является висячей вершиной. Тогда в этом дереве есть висячая вершина, отличная от и что снова приводит нас к нахождению третьей вершины, удовлетворяющей условию. Пусть теперь цикл содержит обе вершины и Тогда ребро, которое мы добавили — это ребро Удалив любое другое ребро, получим новое дерево, в котором одна из вершин или не является висячей, а, следовательно, найдем еще одну вершину, которую можно будет удалить.