Even paths in graph
Source: IOM 2017 #2
September 5, 2017
graphcombinatorics
Problem Statement
In a country there are two-way non-stopflights between some pairs of cities. Any city can be reached from any other by a sequence of at most flights. Moreover, any city can be reached from any other by a sequence of an even number of flights. What is the smallest for which one can always claim that any city can be reached from any other by a sequence of an even number of flights not exceeding ?