Combinatorics · Graph theory · Connected components · Connectivity · Cut vertex · Spanning subgraphs
Problem 4, 2012
The capital of a certain country is joined by a direct air route to each of the other \(2012\) cities. Moreover, every one of those \(2012\) cities is joined by an air route to at least one city other than the capital. Prove that \(1006\) of the air routes leaving the capital can be cancelled in such a way that it is still possible to travel from any city to any other along the surviving routes.
(Every air route may be flown in both directions.)
Sign in to check answers, open hints, read the full solution, and track your progress. Statements are always free.
Serbian National Competition (Drzavno takmicenje) 2012, high school grade I, category A, problem 4. Organized by the Mathematical Society of Serbia (DMS). Source