Изменения

Если <tex>G</tex> имеет простой цикл, то он является отдельной компонентой <tex>K_3</tex> по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения <tex> p = q + 1 </tex> должно быть не более одной компоненты отличной от <tex>K_3</tex>, так как в <tex>K_3</tex> <tex> p = q = 3 </tex>. Если это дерево содержит простой путь длины 2, то в <tex>G</tex> можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является <tex>K_1</tex> или <tex>K_2</tex>. Значит <tex>G</tex> является <tex>K_3 \cup K_1</tex> или <tex>K_3 \cup K_2</tex>, которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если <tex>G</tex> ациклический и <tex> p = q + 1 </tex>, то из <tex> 4 \Rightarrow 5 </tex> и <tex> 5 \Rightarrow 6 </tex> верно, что <tex>G</tex> — связен. В итоге получаем, что <tex>G</tex> является деревом по определению.

* ''Харари Ф.'' Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6