Изменения

* <tex> 1 \Rightarrow 2 </tex> Граф связен, значит поэтому любые две вершнины соединены путем, . Граф ацикличен, значит путь единственен, а так же прост, так как поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.

* <tex> 2 \Rightarrow 3 </tex> Очевидно, что граф связен. Докажем по индукции, соотношение <tex>p = q + 1</tex>. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает граф <tex> G </tex> несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точност точности две компоненты. По предположению индукции в каждой компоненте число вершин на еденицу больше числа ребер. Таким образом, <tex> q = p - 1 </tex> или <tex> p = q + 1 </tex>.

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

* <tex> 6 \Rightarrow 7 </tex> Докажем, что любые две вершины графа соеденены единственной простой цепью, а тогда поскольку <tex> 2 \Rightarrow 3 </tex>, получим <tex> p = q + 1 </tex>. Очевидно, любые Любые две вершины соединены простой цепью, так как <tex>G</tex> — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться <tex> K_3 </tex>, так как иначе добавив ребро, соединяющее две вершины цикла мы получим более одного простого цикла, что противоречит условию. <tex> K_3 </tex> является собственным подграфом <tex>G</tex>, поскольку <tex>G</tex> не является <tex> K_p </tex> для <tex> p \ge 3 </tex>. <tex>G</tex> — связен, а значит есть вершина смежная с <tex> K_3 </tex>. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф <tex>G</tex> является <tex>K_p</tex> для <tex> p \ge 3 </tex>, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соеденены единственной простой цепью, что и требовалось.

* <tex> 7 \Rightarrow 1 </tex> Если <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> можно добавить ребро так, что образуется 2 простых цикла. Следовательно, этим деревом является <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> является деревом по определению.