MathDB

Supppose that there are roads

AB

and

CD

but there are no roads

BC

and

AD

between four cities

A

B

C

, and

D

. Define restructing to be the changing a pair of roads

AB

and

CD

to the pair of roads

BC

and

AD

. Initially there were some cities in a country, some of which were connected by roads and for every city there were exactly

100

roads starting in it. The minister drew a new scheme of roads, where for every city there were also exactly

100

roads starting in it. It's known also that in both schemes there were no cities connected by more than one road. Prove that it's possible to obtain the new scheme from the initial after making a finite number of restructings.
(Т. Зубов)
Thanks to the user Vlados021 for translating the problem.

Problem Statement