Red Rockets and Blue Boeings
Source: South African MO 1996 Q4
May 27, 2012
graph theorycombinatorics unsolvedcombinatorics
Problem Statement
In the Rainbow Nation there are two airways: Red Rockets and Blue Boeings. For any two cities in the Rainbow Nation it is possible to travel from the one to the other using either or both of the airways. It is known, however, that it is impossible to travel from Beanville to Mieliestad using only Red Rockets - not directly nor by travelling via other cities. Show that, using only Blue Boeings, one can travel from any city to any other city by stopping at at most one city along the way.