Some pairs of towns are connected by a road. At least 3 roads leave each town. Show that there is a cycle containing a number of towns which is not a multiple of 3.
Solution
Take any town T1. Now having found T1, T2, ... , Ti take Ti+1 distinct from T1, T2, ... , Ti such that there is a road from Ti to Ti+1. Since there are only finitely many towns, this process must terminate at some Tn. Since Tn has at least 3 roads and the chain cannot be extended there must be at least two towns Ta and Tb with roads to Tn in the chain (apart from Tn-1). wlog a < b. Now consider the cycles:
Ta, Ta+1, ... , Tn length n-a+1
Tb, Tb+1, ... , Tn length n-b+1
Ta, Ta+1, ... , Tb, Tn length b-a+2
Now (n-a+1) - (n-b+1) - (b-a+2) = -2, which is not divisible by 3, so at least one of the cycles must have length not divisible by 3.
© John Scholes
jscholes@kalva.demon.co.uk
4 March 2004
Last corrected/updated 4 Mar 04