304
правки
Изменения
Нет описания правки
* <tex> 3 \Rightarrow 4 </tex> Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.
* <tex> 4 \Rightarrow 5 </tex> <tex>G</tex> — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то <tex> p = q + k </tex>, где <tex>k</tex> — число [[Отношение связности, компоненты связности|компонент связности]]. Поскольку <tex> p = q + 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> связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.
