Details

During my study of graph theory I found this very interesting game. A few years ago I got interested in the four-color theorem and found out that the four-color problem is equivalent to the statement that it is always possible to win this game.

In 1931, H. Whitney proved that the four-color problem is equivalent to the problem of finding a common 4-coloring for two arbitrary -gon triangulations [1].

The basic idea of my attempt to prove the four-color theorem on triangulated graphs was to relate the four-color problem to some property of the graph that is generated on the set of triangulations by connecting two triangulations if there exists a diagonal flip that turns one into the other. This graph is the skeleton of the associahedron or Stasheff polytope in -dimensions.

To see the connection to the four-color problem, think of all possible 4-colorings of a triangulation to be characterized by coloring the diagonals with two colors: green and red. For the moment, forget about the black diagonals. If the vertices of the quadrangle corresponding to a diagonal have four different colors, then the diagonal is red; if they have only three colors then the diagonal is green. All possible ways of coloring the diagonals with red and green correspond to all different 4-colorings of the triangulation. It is easy to see that by flipping a green diagonal, the adjacent diagonals change from green to red and from red to green, while the color of the other diagonals stays unchanged. So if for two arbitrary triangulations there is a diagonal coloring that leads from one triangulation to the other only by flipping green diagonals (a proper path), then we have found a common 4-coloring.

The reverse is also true. If two arbitrary triangulations have a common coloring, then there is a proper path between them. To see this, think of the set of all triangulations that can have a certain 4-coloring as forming a subgraph (a color graph) of the skeleton of the associahedron. What needs to be shown is that all color graphs are connected. We do this by complete induction.

Every diagonal can be assigned a facet of the associahedron that is formed by all triangulations that have this diagonal. Call the diagonals that divide the -gon into an -gon and a triangle spikes. The corresponding facet of a spike is an -dimensional associahedron, and the intersection of a color graph with the facet of a spike is a color graph in the -dimensional associahedron. If two spikes do not intersect, then the corresponding facets intersect in an -dimensional associahedron.

By induction, we assume that each color graph is connected for the associahedrons up to -dimensions. If two triangulations have a common coloring and a common diagonal, there is a proper path between them, due to the induction assumption. For two triangulations that have no diagonal in common, there are always two spikes that do not intersect: one, , from the first triangulation and another, , from the second. Therefore, the color graph of a common 4-coloring of two such triangulations has three subgraphs: the intersections and of the color graph with the facet corresponding to and , as well as the intersection of the color graph with the intersection of the facets corresponding to and . Since , , and are color graphs of lower dimension, they are connected, by the induction assumption. However, since is connected to , and is connected to , is connected to . Therefore, there is a proper path between the two triangulations if they have a common 4-coloring. QED

The black diagonals are introduced to have a nicer way to play the game. An equivalent form would be: can you choose a diagonal coloring that allows a proper path from one triangulation to the other? With the help of the black diagonals, the diagonal coloring is done implicitly.

References

[1] H. Whitney, "A Theorem on Graphs," Annals of Mathematics, 32(2), 1931 pp. 378–390. www.jstor.org/stable/1968197.

[2] J. A. De Loera, J. Rambau, and F. S. Leal, Triangulations of Point Sets, 2004. www.wm.uni-bayreuth.de/fileadmin/Lehre/obsolete/TriangulierungVonPunktmengenUndPolyedern/TriangBook_motivation.pdf.