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 .
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
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
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
of the color graph with the facet corresponding to
, as well as the intersection
of the color graph with the intersection of the facets corresponding to
are color graphs of lower dimension, they are connected, by the induction assumption. However, since
is connected to
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.