On the four and five color theorems

The five color theorem for planar maps is considerably easier to prove than the four color theorem. The essential part of the proof is the Kempe-Heawood swap: given coloring of a map, choose two countries with common border and swap their colors in the connected component of the countries of the two colors. The swap obviously produces new coloring of the map. The question is: are all four (or five) colorings of a planar graph connected by a sequence of swaps?

This problem somewhat resembles solving the Rubik's cube.

The question can be generalized to n colorings of an arbitrary graph.

Solution 1:

I think I have solved the problem for all numbers of colors $n\ne 5$.

For a graph $G$ consider the graph $G_n$, whose vertices are $n$-colorings of $G$ and whose edges are pairs of colorings that can be obtained from each other by a Kempe-Heawood swap. The question: "Is $G_n$ connected?"

We can assume that $G$ is connected itself, because for any $n$ connectedness of $G_n$ is equivalent to connectedness of $K_n$ for all components $K$ of $G$.

$n = 1$ or $2$

In the case $n=1$ we have $|G_1|\le 1$, so $G_1$ is obviously connected. In the case $n=2$ if $G_2$ is non-empty, then $G$ is a connected bipartite graph, which can be colored only in two different ways, connected by an all-vertices Kempe-Heawood swap. So when $n\le 2$ the answer is positive for all graphs, not planar only.

$n \ge 3$, non-planar case

The answer is negative and here is a counterexample, inspired by the planar case for $n=3$. Consider the graph $G$, whose vertices are the elements of $\{0,1\}\times\{0,1,\cdots,n-1\}$, and $a=(1,y_1)$ and $b=(0,y_2)$ are connected by the edge iff $y_1-y_2$ is not $0$ or $1$ modulo $n$. $(x,y_1)$ and $(x,y_2)$ are connected by the edge for any $x,y_1,y_2$. There is a coloring with colors $0,1,\cdots,n-1$, which just color the vertex $(x,y)$ into $y$. Also there is another coloring such that $(0,y)$ is colored into $y$ and $(1,y)$ into $y-1$ modulo $n$. We excluded exactly those edges from the full graph for this two colorings to be correct.

However, any Kempe-Heawood swap of the first given coloring just renames the two colors. Indeed, $(0,a),(1,a),(0,b),(1,b)$ are all the vertices of the colors $a$ and $b$, $(0,a)$ and $(0,b)$ are connected, $(1,a)$ and $(1,b)$ are connected, and for $a\ne b$ it cannot be the case that $a-b$ and $b-a$ are both $1$ modulo $n\ge 3$, so $(0,a),(1,a),(0,b),(1,b)$ lie in the same Kempe-Heawood chain. Therefore, any swap preserves the fact that $(0,y)$ and $(1,y)$ are of the same color, but this doesn't hold for the second given coloring. Thus, $G_n$ is not connected.

$n = 3$, planar case

For $n=3$ the construction above yields the following two colorings:

$n = 4$, planar case

Unfortunately, the constructed counterexample is not planar for $n\ge 4$. Nevertheless, here is a planar counterexample for $n=4$:

This is a projection of a cube, augmented by 6 extra edges. On the left picture the opposite vertices of the cube are of the same color. It is straightforward to verify that after any swap this property holds. However, this is not true for the right picture, thus $G_4$ is not connected for this graph.

$n=5$, planar case

I don't have a working idea how to approach it. I tried to consider the dodecahedron projection with symmetric 5-coloring (the vertices of every color form a tetrahedron), but then it's impossible to add edges in such a way that graph remains planar and for all swaps all the vertices of the swap colors lie in the same component.

$n\ge 6$, planar case

The answer is positive (okay, at least for finite graphs, I didn't thought about infinite case much), and this is pretty easy to prove by induction on number of vertices in $G$. Base $|G|=1$ is trivial. Now let us have two $n$-colorings $A$ and $B$ of the graph $G$. There is a vertex $x\in G$ with degree not greater than $5$, because $G$ is planar. Consider the graph $G-x$ and restrict both $A$ and $B$ on it. By induction hypothesis, there exists a series of swaps, sending $A$ to $B$ in $G-x$.

Let us try to perform it in the graph $G$, ignoring $x$. The only case where we can't ignore $x$ is when we are trying to swap colors $a$ and $b$, $x$ is of the color $a$ and has at least two neighbors of the color $b$, thus decreasing the number of components in a full subgraph of colors $a$ and $b$, comparing to $G-x$. However, this means, there are not greater than 4 colors among the neighbors of $x$. Therefore, there exists a color such that neither $x$, nor its neighbors are of that color. We can swap $a$ and this sixth color on the component, consisting of the vertex $x$. After that, $x$ doesn't interfere with intended swap of $a$ and $b$ anymore, and we can proceed further on $G-x$.

So we can turn $A$ into $B$ modulo vertex $x$. But the thing is, even if $x$ now is not of the same color than in $B$, we can swap the resulting color of $x$ with the color of $x$ in $B$ and obtain $B$, qed.

P.S. I hope someone will correct all mistakes in my English and remove this post scriptum.