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

After looking at this for a while, I think I found a possible loophole rendering the proof disprovable.

Say town A is in Alexton and town B in Brighton.  There are 11 roads connecting the two.  This obviously doesn't work out and was not how it was meant to be.

I think where it says "It is known that no town is connected with more than 10 others." it should actually say "It is known that no town is connected with more than 10 roads."  I think that with this wording it may be provable.  On the other hand, I'm not sure how to actually prove it yet.

Aaron could also have meant that no two roads connect the same two towns, as the previous commenters have interpreted it, but I think we can go a little further.

Posted by Tristan on 2004-03-05 17:28:12