This paper will reduce the 4CT from the realm of all planar graphs to a single
graph, a chordless cycle graph of order 5.
Four-color Theorem; 4CT: Every planar graph is four-colorable.
First Simplification: If 4CT is true for all maximal planar graphs; then it is true
for all planar graphs.
Second Simplification: The 4CT is true if there is no minimal counter-example (MCE).
Graph G is a MCE if,
1) G is a planar graph,
2) G is not 4-colorable;ie, Chi(G) > 4, and
2) Every planar graph with fewer vertices than G is 4-colorable.
Third Simplification: G is a simple, loopless, maximal planar graph.
Then G will have at least one vertex with degree = 5. By Euler's formula, the
average degree of a maximal planar graph is < 6. Therefore, at least one vertex
must have degree < 6. A critical parameter of the MCE is that all vertices have
degree => 5.
Let 'V' be a 5-degree vertex in G. Figure 1 shows this
A--B--C
|\ | /|
| \|/ |
| V |
| / \ |
|/ \|
E-----D
Figure 1
Figure 1 is in essence, an induced subgraph of G. Graph (G-V) is defined as the
induced subgraph of G that results when vertex V is removed from G. Figure 2 then
is an induced subgraph of graph (G-V).
A--B--C
| |
| |
| |
| |
| |
E-----D
Figure 2 Graph C
(G-v) has fewer vertices than G. Therefore, (G-v) must be 4-colorable. But G
cannot be 4-colorable. The only difference between (G-v) and G is vertex 'V'!
Therefore, the addition/removal of V makes Chi(G)=5 and Chi(G-V)=4. This is
possible only if;
There is no 3-coloring of the vertices of Graph C that will extend to a proper
4-coloring of (G-V)!
Fourth Simplification: G is not an MCE if Graph C is 3-colorable!
It would be folly to to try to prove this conjecture. Therefore, for the moment;
assume that (G-V) is 4-colorable only when C is 4-colored. There are only five
different 4-coloings for C. These colorings are defined by the specific pair of vertices that are assigned the same color. In Figure 3, the vertices have been
assigned colors to facilitate the following discussion.
1 2 3
A--B--C
| |
| |
| |
E-----D
4 2
Figure 3
One to force a specific coloring pattern on a specific set of vertices is with
adjacency and/or Kempe chains? The pattern assigned to Figure 3 is achieved by;
1) A {13} chain between v_A & v_C, and
2) A {34} chain between v_C & v_E, and
3) A {232} chain between v_B & v_D!
Normally Kempe Chains do not intersect, but the {232} chain can cross the {13} and
{34} chains at a common "1" vertex.
This is not the only 4-coloring pattern for Figure 3 that extends to a proper
4-coloring of (G-v)! Every 4-coloring of Figure 3 must extend to a proper
4-coloring of (G-v)!
1 2 3 1 2 3
A--B--C A--B--C
| | | |
| | | |
| | | |
E-----D E-----D
4 2 4 1
Figure 3 Figure 4
1 2 3 2 4
A----------B----------C-----------D----------E
| | / \ | |
| | / \ | | AC 1/3
| | / \ | | CE 3/4
|----------3------1 4-------3----------| BD 2/3/2
| |
|----------2-----------|
Figure 5
1 2 3 1 4
A----------B----------C-----------D----------E
| \ \ | /|
| \ \---------4--------3 |
| \ | |
| \ 1 | AD 1/4/1
| \-----------------4----------2 BE 2/4
| | CE 3/4
|---------------------------------|
Figure 6
Can Figure 5 be morphed into Figure 6 using only Kempe coloring rules? That is.
without creating a valid interim 3-coloring?
Suppose that an edge is added between v_B and v_D? Now C and (G-V+BD) are not
properly colored! Graph C cannot be properly colored unless v_B and v_D are
assigned different colors. If C cannot be properly 4-colored, then (G-V+BD)
cannot be properly 4-colored. Since (G-v+BD) has fewer vertices than G, if
(G-V+BD) is not 4-colorable, then G is not minimal and is cannot be an MCE.
It possible that C has two external chords. But these cannot prevent a second
internal chord between either B & E or A & D! The addition of a second internal
chord will make recoloring C more difficult but not necessarily impossible!
Assume that chords {BD} and {BE} are added and a proper recoloring is available
as shown in Figure 4.
1 2 3
A--B--C
| / \ |
|/ \|
E-----D
4 1
Figure 4
Now chord {BE} is replaced by chord {AD}. This necessitates a second recoloring;
which triggers a second chord adjustment. It is possible that chord adjustment
followed by recoloring can continue indefinitely. If this is true, then it may
be that every 4-coloring of C extends to a proper 4-coloring of (G-V+2).
It can be argued that this is possible only if there are also 3-colorings of C
that are also extendable to proper 4-colorings of (G-V+2).
Summary: The four color theorem has been essentially reduced to the contemplation
of the following questions;
1) Are there configurations of G for which there are 3-colorings of C that are
extendable to a proper 4-coloring of (G-v)? If 1) is true, then G is 4-colorable
2) If 1) is false, are there any configurations of (G-v+2) that are not 4-colorable?
If 2) is true, then G is not minimal
3) If 2) is false, then is it neccessary that ALL possible 4-colorings of
C extend to proper 4-colorings of (G-v)? If 3) is false, the 4CT is indeterminate.
4) If 3) is true, does this imply that some 3-colorings of C extend to proper
4-colorings of (G-v)? If 4) is true, then G is 4-colorable