MathDB

6

Part of 2022 Korea National Olympiad

Problems(1)

Islands and the Bridges

Source: KMO 2022 P6

10/29/2022
n(≥4)n(\geq 4) islands are connected by bridges to satisfy the following conditions:
[*]Each bridge connects only two islands and does not go through other islands. [*]There is at most one bridge connecting any two different islands. [*]There does not exist a list A1,A2,…,A2k(k≥2)A_1, A_2, \ldots, A_{2k}(k \geq 2) of distinct islands that satisfy the following: For every i=1,2,…,2ki=1, 2, \ldots, 2k, the two islands AiA_i and Ai+1A_{i+1} are connected by a bridge. (Let A2k+1=A1A_{2k+1}=A_1)
Prove that the number of the bridges is at most 3(n−1)2\frac{3(n-1)}{2}.
combinatoricsgraph theorycycle