Albinia consists of two states: Alexton and Brighton. Each road in Albinia connects two towns from Alexton and Brighton respectively. It is known that no town is connected with more than 10 others.

Prove that it is possible to color all roads in Albinia, using 10 colors, in such a way that no two adjacent roads would be the same color (we call two roads adjacent if they leave the same town).

Is it provable? This question reminds me of the old "Colour any map with just four colours" question, which, to the best of my belief, is as yet unproved.

Posted by Iain on 2004-03-22 16:23:29