Пусть между городами A, B, C и D есть дороги AB и CD, но нет дорог BC и AD. Назовем перестройкой замену пары дорог AB и CD на пару дорог BC и AD. Изначально в стране было несколько городов, некоторые пары городов были соединены дорогами, причем из каждого города выходило по 100 дорог. Министр нарисовал новую схему дорог, в которой из каждого города по-прежнему выходит 100 дорог. Известно, что как в старой, так и в новой схемах никакие два города не соединены более, чем одной дорогой. Докажите, что новую схему можно получить из старой с помощью нескольких перестроек.
Рассмотрим множество M, состоящее из всех возможных 100-регулярных графров на данном множестве вершин V (наши две схемы дорог — среди них). Докажем что любые два графа из М можно перевести друг друга серией перестроек. Для двух графов 
пусть 
—
Очевидно 
четно, а в 
поровну рёбер из G и 
Предположим, что существуют пары непереводимых друг в друга перестройками графов в M и рассмотрим такую пару графов 
с минимальным 
Граф 
имеет в каждой вершине поровну рёбер из A и из B. Следовательно, в H существует чередующийся цикл — в котором рёбра A и B чередуются. Рассмотрим минимальный такой цикл 
(это не обязательно простой цикл, вершины в нем могут повторяться). Первая наша цель — найти на этом цикле четыре последовательные различные вершины. В самом деле, пусть среди a1, a2, a3, a4 есть совпадающие. Очевидно, возможно лишь совпадение 
Так как рёбра цикла не повторяются, тогда 
и в качестве искомой четверки подойдет a2, a3, a4, a5.
Итак, не умаляя общности будем считать, что все вершины a1, a2, a3, a4 различны, причем 
и 
Рассмотрим три случая.
a) Когда 
Тогда проведем перестройку 
в графе B (возможно, так как 
и получим
По предположению, C можно получить из A перестройками, значит, можно получить и B.
b) Когда 
Тогда 
—
c) Когда 
Тогда проведем перестройку в графе A (возможно, так как 
и получим граф C с
По предположению, C можно получить из B перестройками, значит, можно получить и A.