Colorful Mathematics: Part IV

Feature Column Archive

4. From schoolgirls to tournaments

The following problem has come to be called the Lucas' (1842-1891) Schoolgirls Problem. Lucas is best known for his posing of the Tower of Hanoi Problem (1883). Consider the situation sometimes seen in primary schools when students line up in pairs and walk into the auditorium. Given an even number (2s) of students who walk in pairs, what is the largest number of days they can take such walks so that no pair of girls walks together on more than one day? This problem can be solved by thinking about the complete graph on an even number of vertices, K2s. This is the graph where one has 2s vertices each joined to every other one. It is not difficult to see that a coloring of the edges of this graph matches pairs of students and that one gets a different matching corresponding to each of the colors in an edge-coloring with a minimal number of colors. Thus, since the minimal number of colors required to color K2s is 2s - 1, one can have 2s girls walk in pairs without a repeat for 2s - 1 days.

What is the chromatic index, the minimum number of colors to color the edges of a graph, for a complete graph with n vertices? The answer depends on whether n is even or odd:

When n is odd, the chromatic index of the complete graph on n vertices is n;
When n is even, the chromatic index of the complete graph on n vertices is n - 1.

The way to construct a coloring can be seen by generalizing what is done for the example of n = 5 and n = 6. Begin by drawing a regular n-gon, where n is odd, and form a complete graph by adding the necessary edges. Now one uses n colors to color the boundary of the regular n-gon and and, for a fixed edge on the boundary, colors all of the other edges parallel to the edge in the complete graph the same color as shown below:

A 5-cololring of the edges of the complete graph on 5 vertices


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:

A 5-coloring of the edges of the complete graph on six vertices

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.

The discussion above also shows how to design a round robin tournament with a minimum number of rounds. The goal in a round robin tournament is to have each team (player) play every other team exactly once. For an even number of teams, n = 2s, one needs 2s - 1 rounds, where in each round the teams with the same edge color are paired. For an odd number of teams there will be 2s- 1 rounds, with one team getting a "bye" (i.e. that team does not play that round) in each round, and the teams that play a given round are those paired by edges with the same color.

Another simple-to-state result that was first demonstrated without any applications context was discovered in 1916 by Denes König (1884-1844), and has proved to be significant in applied coloring problems.

The result states that if G is a graph (several edges between a pair of vertices being allowed) whose vertices can be colored with two colors (bipartite graph), then the minimum number of colors to color the edges of G is equal to the maximum valence (defined in an earlier column) of any vertex in the graph.

For example, the graph below shows a bipartite graph with maximal valence three. The graph has been three edge-colored. Although the graph below has all its vertices having the same valence this is not necessary for König's Theorem to apply.


A 3-coloring of the edges of a bipartite graph with maximum valence 3


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.

  1. Introduction
  2. Resolving conflicts (I)
  3. Resolving conficts (II)
  4. From schoolgirls to tournaments
  5. Mathematics and cell phones
  6. References