TOT 298 1991 Spring A S5 system of roads fro 16 cities
Source:
June 9, 2024
combinatorics
Problem Statement
There are cities in a certain kingdom. The king wants to have a system of roads constructed so that one can go along those roads from any city to any other one without going through more than one intermediate city and so that no more than roads go out of any city.
(a) Prove that this is possible.
(b) Prove that if we replace the number by the number in the statement of the problem the king’s desire will become unrealizable.(D. Fomin, Leningrad)