Problem

Source: 2023 Taiwan TST Round 1 Independent Study 2-C

Tags: graph theory, Taiwan, combinatorics



There are $n$ cities on each side of Hung river, with two-way ferry routes between some pairs of cities across the river. A city is “convenient” if and only if the city has ferry routes to all cities on the other side. The river is “clear” if we can find $n$ different routes so that the end points of all these routes include all $2n$ cities. It is known that Hung river is currently unclear, but if we add any new route, then the river becomes clear. Determine all possible values for the number of convenient cities. Proposed by usjl