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

http://www.ams.org/new-in-math/cover/colorapp4.html

Also Robin J. Wilson's book "Introduction to Graph Theory," 4th ed., pp. 94-95 for a short proof.

This problem is an instance of a theorem of graph theory attributed to Denes Koenig, c. 1916.

Posted by Richard on 2004-03-05 19:05:46