Problem

Source: Swiss TST 2015. Problem 11

Tags: Connected graphs, combinatorics



In Thailand there are $n$ cities. Each pair of cities is connected by a one-way street which can be borrowed, depending on its type, only by bike or by car. Show that there is a city from which you can reach any other city, either by bike or by car. Remark : It is not necessary to use the same means of transport for each city