Wolfram Demonstrations Project

The goal of this game is to turn the black triangulation into the underlying blue one. Each diagonal can be in three different states: green (it can rotate), red (it cannot rotate), or black (it is undefined). At the beginning of the game there are an equal number of black and blue diagonals and no green or red diagonals. Click a black diagonal to make it green.

Any given diagonal will be bounded by a single quadrilateral. That quadrilateral has a second diagonal. A rotation of a diagonal switches to the other diagonal of the quadrilateral.

The crucial point is that each rotation of a diagonal also causes the adjacent diagonals to change from green to red and from red to green, while black diagonals stay black.

The game is over when each diagonal lines up with the underlying diagonals in blue.

Contributed by: Fabian Lackner

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

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