Colorful Mathematics: Part IV
4. From schoolgirls to tournaments
To handle the case of an even number of vertices, add a vertex to the coloring for the odd number with one less vertex, and color the extra edges as shown below for the case when n = 6:
For the 6 students represented in the diagram above, they can walk in pairs for 5 days. On day one have the pairs matched by the blue edges walk together, on day two have the pairs matched by the red edges walk together, etc. This construction can be generalized for any odd value of n, and, thus, for any even value of n. However, once we see that the Lucas problem can be solved by finding the chromatic index of a complete graph, we realize that we can apply what we have seen to a different, perhaps more common, situation.
Recent ideas involving the design of optical communications networks have led to a variety of new edge-coloring problems (see Peter Winkler's abstract at the top of the link) including conjectured generalizations of König's Theorem.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance