Cities and airlines
Source: St Petersburg Olympiad 2012, Grade 11, P7
September 29, 2017
combinatoricsgraph theory
Problem Statement
Some cities of Russia are connected with some cities of Ukraine with international airlines. The Interstate Council for the Promotion of Migration intends to introduce a one-way traffic on each airline so that, by taking off from the city, it could no longer be returned in this city (using other one-way airlines). Prove that the number of ways to do this is not divided by .