Destroying the roads
Source: St Petersburg Olympiad 2014, Grade 11, P2
October 24, 2017
combinatorics
Problem Statement
There are cities in country, and some cities are connected by roads. Not more than roads go from every city. Set of roads is called as ideal if all roads in set have not common ends, and we can not add one more road in set without breaking this rule. Every day minister destroy one ideal set of roads.
Prove, that he need not more than days to destroy all roads in country.