Эйлеровы графы

Рассмотрим граф , в котором вершины — это города, а рёбра — дороги. Степени всех вершин этого графа равны 100. Начнем ходить из произвольной вершины графа. Будем ходить по ранее не пройденным ребрам, пока можем. Если мы в какой-то момент не сможем выйти из вершины, то мы прошли все 100 ребер, выходящих из нее. Предположим, что эта вершина, отличная от стартовой. Тогда число входов в вершину на 1 больше числа выходов, следовательно мы посетили нечетное число ребер, выходящих из вершины (каждый вход и выход добавляет одно ребро). То есть мы зациклились. Выкинем все ребра этого цикла. У каждой вершины степень по-прежнему четна. Опять найдем цикл, выкинем все его ребра и так далее.

В итоге мы разбили ребра графа на не пересекающиеся по ребрам циклы. На каждом цикле зададим направление обхода (поставим на ребрах стрелочки, идущие в одном направлении). Тогда в каждую вершину входит 50 ребер и из каждой вершины выходит тоже 50 ребер. Разобьем все ребра, выходящие из каждой вершины, на 5 пучков. Тогда все рёбра графа G разобьются на пучки, что и требовалось.