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).

Um....never mind...Two roads are adjacent if they leave the same town.....

 

Are we to assume that Alexton and Brighton are neat and tidy divisions of Albinia ? Because if I were allowed to "gerrymander" Albinia wildly enough into odd shaped fragments, and then arbitrarily unite the fragments into two states Alexton and Brighton, I'm pretty sure I could come up with a map that would not permit your puzzle's hypothesis.    

Edited on March 5, 2004, 5:46 pm

Posted by Penny on 2004-03-05 11:18:44