TOT 018 1982 Spring J4 air routes between 101 towns
Source:
August 17, 2019
combinatorics
Problem Statement
In a certain country there are more than towns. The capital of this country is connected by direct air routes with towns, and each town, except for the capital, is connected by direct air routes with towns (if is connected with is connected with ). It is known that from any town it is possible to travel by air to any other town (possibly via other towns). Prove that it is possible to close down half of the air routes connected with the capital, and preserve the capability of travelling from any town to any other town within the country. (IS Rubanov)