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

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