Graph K_m (m = 1990 > 2^10) has mono. odd circle length
Source: IMO ShortList 1990, Problem 22 (ROM 4)
August 15, 2008
graph theorycombinatoricsExtremal combinatoricsExtremal Graph TheoryIMO Shortlist
Problem Statement
Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.