Airline connections
Source: Baltic Way 2014, Problem 10
November 11, 2014
combinatorics proposedcombinatorics
Problem Statement
In a country there are airports. Super-Air operates direct flights between some pairs of airports (in both directions). The traffic of an airport is the number of airports it has a direct Super-Air connection with. A new company, Concur-Air, establishes a direct flight between two airports if and only if the sum of their traffics is at least It turns out that there exists a round-trip of Concur-Air flights that lands in every airport exactly once. Show that then there also exists a round-trip of Super-Air flights that lands in every airport exactly once.