Problem

Source: 2015 Final Korean Mathematical Olympiad Day 1 Problem 3

Tags: graph theory, combinatorics



There are at least $3$ subway stations in a city. In this city, there exists a route that passes through more than $L$ subway stations, without revisiting. Subways run both ways, which means that if you can go from subway station A to B, you can also go from B to A. Prove that at least one of the two holds. $\text{(i)}$. There exists three subway stations $A$, $B$, $C$ such that there does not exist a route from $A$ to $B$ which doesn't pass through $C$. $\text{(ii)}$. There is a cycle passing through at least $\lfloor \sqrt{2L} \rfloor$ stations, without revisiting a same station more than once.