Question 108
In a certain country that the system of airlines is connected (That is, from each city one can reach each other city by some flights). It appears that for each Cyclic Route Containing An Odd Number of Airlines not connected. Prove that one can distribute all the cities into 4 regions so that each airline links two cities from different regions. (A region may container no cities.) (V. Dol'nikov) In the country, some pairs of cities are connected by two-way non-stop flights. At the same time, from any city you can fly to any other (possibly with transfers). It is known that if you choose any closed route from an odd number of flights and close all these flights, then it will not be possible to get to any other city from any city. Prove that all cities can be divided into 4 republics so that any flight connects cities from different republics. (Some republics may not contain cities.) (V. Dolnikov)