Four color theorem: almost there?


Here there are some results that came out from the study of Kempe chains/cycles (of edges) in Tait coloring of a 3-regular planar graph.

Next is shown an image with a summary of the ideas behind this approach. I didn’t have the time to re-create this into computerized images. I will do it later. Soon will follow the F5 case for the part I’ve been experimenting with success (sub-condition where the two edges lies on two different Kempe-cycle – see below).

kempe-half-cycle-swapping-method

Here is the F4 case shown a little better:

kempe-half-cycle-swapping-method-F4

And here some deeper details of these ideas.

Theorem: In a well edge-colored (Tait coloring) 3-regular planar graph all Kempe chains are cycles

  • This can be easily proved showing that, once colored, the edges of any vertex use all the three colors (for example R, G, B), so if you are following the path of a Kempe chain, as for example an (G, B)-Kempe chain, the chain itself cannot end to a vertex, because one of the other two edges continues the kempe chain, unless that edge was exactly the first edge you started following the path of the chain … making it a Kempe cycle, as for example the (G, B)-Kempe cycle of this picture
  • Note: This theorem, in this form, is valid if the graph is already well colored (three colors). Consider that to say that the edges of a graph can be well colored (using three colors) is as difficult to prove as the four color theorem for the faces of a map. Never the less this result can be used to search a short proof of the four color theorem, even if it depends on the long proof ;-). Or (better) this result can be used without this dipendency on the long version, immerged in the reduction method when restoring the edges one at a time. As long as you solve the N+1 case (restore of F2, F3, F4, F5), starting from the map with only two faces (the island and the ocean surrounding it) the theorem is true
kempe-cycle

Picture-01: All Kempe-chains are Kempe-cycles

Steps and results toward a short proof of the 4ct:

  • Simplify the map removing one edge from one of the faces with 2, 3, 4 or 5 edges. Repeat this procedure until the map will have just one country left. This simplification procedure can be always done because the set { F2, F3, F4, F5 } represents an unavoidable set, so every 3-regular planar graphs has to have at least one face of the type included in the set
    • The procedure, for a simple map, is shown in the previous post: here
    • The idea is similar to the “patching” method used by Kempe, in which a “patch” with the same shape but a bit larger of a face (F2, F3, F4 or F5), was put over the face to shrink it down to a point. You can read the original paper here: On the Geographical Problem of the Four Colours
  • In reverse order, restore the edges that were removed, one at a time. Each time an edge is restore, we can face one of these conditions:
    • the edge restores an F2 – Note: particular and trivial case (see next point)
    • the edge restores an F3 – Note: trivial case
    • the edge restores an F4 – Note: Easy to handle
    • the edge restores an F5
  • F2 as a trivial case
    • When the restored edge reestablish an F2 face, it means the vertices of the resored edge, touch a single edge and so you have a spare color to use to solve this case (HAPPY END)
  • For all previous conditions (F2 can be seen as a particular case) there are two main possibile sub-conditions
    • CONDITION-1: The two edges touched by the restored edge are on a common Kempe cycle
      • If the two edges belong to a Kempe-cycle, the solution is easy. Apply a Kempe-chain color swapping to half (one of the two parts of the cycle being “cut” by the restored edge) of the cycle to solve this case (HAPPY END)
      • Consider that in case of the restored face is an F3, this is always the case, since the two edges touch each other. So also F3 can be regarded as a particular case
    • CONDITION-2: The two edges touched by the restored edge are NOT on a common Kempe cycle, but on distinct cycles … of course with no common edges
      • TBF: This is easy to handle for F4 and of course for F2 and F3 that are particular cases. For the F5 case I’m trying to prove that all cases can be reconducted to CONDITION-1

If this Example-02 the restored edge (in black) reestablish an F5 face. Both the edges (Green = on the left, Red = on the right) do non lie on the same (G-R)-cycle (CONDITION-2). Similar examples can be created when the two touched edges have the same color. In that case you can consider two different Kempe-chain ((R-x)-chain if the edges are colored Red) or you can easily reconduct that case to the one with different colors

kempe-cycle-F5-both-edges-not-on-cycles

Example-02: Example of restoring an F5

Now the diffucult part of the proof about the F5 case where the two edges do not lie on the same Kempe-cycle.

How can I reconduct a CONDITION-2 (edges NON on the same Kempe-cycle) to a CONDITION-1 (edges on the same Kempe-cycle)?

Advertisements

About stefanutti

V: "Do you know me?" S: "yes." V: "No you don't." S: "Okay." V: "Did you see my picture in the paper?" S: "Yes." V: "No you didn't." S: "I don't even get the paper."
This entry was posted in math and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s