Изменения
→Доказательство эквивалентности
* <tex> 4 \Rightarrow 5 </tex> <tex>G</tex> - ациклический граф, значит каждая компонента связности графа является деревом. Если всего <tex> k </tex> компонент, то, поскольку в каждой из них вершин на единицу больше чем ребер, то <tex> q = p + k </tex>. Так как <tex> k = 1 </tex>, то <tex>G</tex> - связен. Таким образом наш граф дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.
* <tex> 5 \Rightarrow 6 </tex> Поскольку <tex> K_p </tex> для <tex> p >= /ge 3 </tex> содержит простой цикл, то <tex>G</tex> не может им являться. <tex>G</tex> связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.
* <tex> 6 \Rightarrow 7 </tex>
