MathDB

1025 cities are connected to each other by 10 airlines

Source: 1984 Polish MO Finals p6

February 25, 2020

combinatorics

Problem Statement

Cities

P_1,...,P_{1025}

are connected to each other by airlines

A_1,...,A_{10}

so that for any two distinct cities

P_k

and

P_m

there is an airline offering a direct flight between them. Prove that one of the airlines can offer a round trip with an odd number of flights.