In Skinien there 2009 towns where each of them is connected
Source: German TST 7, P2, 2009, Exam set by Christian Reiher
July 18, 2009
combinatorics unsolvedcombinatorics
Problem Statement
In Skinien there 2009 towns where each of them is connected with exactly 1004 other town by a highway. Prove that starting in an arbitrary town one can make a round trip along the highways such that each town is passed exactly once and finally one returns to its starting point.