Four color theorem: 3-edge coloring, impasse and Kempe chain color swapping

It is known that for regular maps, “3-edge coloring” is equivalent to finding a proper “four coloring” of the faces of a map.

This post is about coloring impasses, fallacious Kempe chain color swapping (not solving the impasse) and an hypothesis I’d like to verify.

FIRST: What is an impasse

Lets say you are coloring (Red, Green, Blue) the edges of a map and have properly colored a portion of it, as in the example. At a certain point you get to a vertex that has two edges already colored, for example with Red and Green (e1, e2). In this case you’d be forced to select the color Blue for the uncolored edge (ex). But it is possible that the color Blue is already used by one of the other two edges starting from vy (e3). This situation is called impasse. In the example e4 may be already colored or not, the impasse remains.

SECOND: Apply Kempe chain color swapping and problems using it

One technique that can be used to solve an impasse is to apply a Kempe chain color swapping. But the problem is that this Kempe swap does not always work. This happens when the Kempe swap does not only change the color of the edge that caused the impasse (e4), but also the color of one of the other three edges involved in the impasse (e1, e2, e5 in the example).

To better understand Kempe chain color swapping, lets analyze, step by step, the labeled part the graph showed above:

• Impasse: Since e1 and e2 are colored Green and Blue, e3 should be colored Red. But this color can’t be used because Red is already used by e4
• To solve this impasse you can try to apply a Kempe chain coloring swapping
• The possibilities are: (R-G)-chain and (R-B)-chain that change the color of e4
• (R-G)-chain, involving e4 and e5 would not work, because R would end up in e5, not changing the situation … even if the continuation of the chain arrives to the vertex a
• (R-B)-chain has a better chance to work, because would set e4 with color B, sometimes solving the impasse. I said sometimes because this is true only if the (R-B)-chain does not arrive to vertex b, swapping also the color of e2, in which case would simply mirror the problem between the vertices c and d

THIRD: Hypothesis to solve the second impasse when Kempe swap fails

Using the Java application I wrote, I started experimenting Kempe chain color swapping and found many situation where the swapping would not solve the impasse, but I also found a method, which of course needs to be proved, to solve the second impasse when Kempe chain color swapping fails (fallacious Kempe chain color swapping). If true (consider that what is written in this blog are just personal notes about an attempt) this would prove the four color theorem a very short and elegant way.

<insert video>

Hypothesis:

The hypothesis I’d like to verify is that from maps in which F2, F3, F4 faces have been previously removed (which is safe for the proof of the theorem), the fallacious Kempe chain can always be “broken” (or in different words: its path changed) along the way (using another Kempe chain coloring swap) to avoid the second impasse. After this “cut”, the original swap can be performed to solve the original impasse.

I tried this method on many maps with and without F2, F3, F4 faces, and so far it seems to work … always.

Here is an example:

In this example:

• There is an impasse between Vx and Vy. On Vx color Green could be used for the edge connecting Vx and Vy but Green is already used by e4
• (G-R)-chain (…-e4-e3-…) swap does not work because, e4 and e3 will simply swap colors and Vy will still have a Green color starting from it
• (G-B)-chain (e4-e5-…) swap does not work because the chain ends up to e1 (to the vertex Vx) and the impasse will remain
• The hypotesis, that works for this example and all examples I found (maps without F2, F3, F4), is that che (G-B)-chain can be “broken” using a color swapping of the (B-R)-chain at (…-e5-e6-…), and after this swap you can apply the original (G-B)-chain color swap, that will solve the impasse. By contrary I found many example for maps containg F2, F3, F4 in which this hypotesis is not true

To be finished:

• Insert example of maps containing F2, F3 or F4 where the second Kempe chain swap does not solve the impasse
• Insert other examples of impasses with maps without F2, F3, F4
• Insert video examples of impasses with maps without F2, F3, F4, that can be solved by “cutting” the fallacious chain