Подвешивание, ранжирование, упорядочивание в графах

Рассмотрим какую-нибудь компоненту связности этого графа и докажем, что там есть нужный нам цикл. Пусть в ней есть вершина Она соединена как минимум с тремя вершинами. Если эти вершины соединены между собой или какие-то две из них соединены с одной и той же вершиной, отличной от мы получим нужный цикл. Значит, эти вершины соединены минимум с другими вершинами. Аналогично эти вершины соединены с другими вершинами, либо мы нашли нужный цикл и так далее. Заметим, что в процессе рассуждений получается дерево. Если мы таким образом построим уровней, то в графе будет хотя бы вершин, что явно больше Значит, не ниже чем на уровне найдутся две вершины, которые либо соединены между собой, либо соединены с одной и той же вершиной. Но тогда есть цикл длиной меньше чем включающий эти две вершины и