minimal counter-example to the 4CT.
To understand why this is true, we must understand the mce/4CT. The mce/4CT
involves different graphs; or rather, two configurations of the same graph.
One configuration cannot be properly 4-colored, the other must always be
capable of being properly 4-colored. The only difference between the two is
a single 5-degree vertex and 5 edges.
Consider Figure 1
1--2--3 1--2--3
|\ | /| | |
| \|/ | | |
| 0 | | |
| / \ | | |
|/ \| | |
5-----4 5-----4
Figure 1a Figure 1b
The configuration with Figure 1a cannot be properly 4-colored. The configuration
with Figure 1b can always be properly 4-colored.
Figure 1a is an induced subgraph of the simple loopless maximal planar graph G.
G is a candidate mce/4CT. If Chi(G) = 5 it is because Chi(F.1a) = 5. If
Chi(G) = 5 and if Figure 1b is not 3-colorable. then G is an mce/4CT.
Is there a configuration of G that will force vertices v_1 thru v_5 to have
a 4-coloring? NO!
How can we force a 4-coloring on Figure 1a? Two Kempe chains won't do it.
How about three?
|--------------|
|---------| |
A----B----D----B----C
|---------|
Figure 2
|--------------|
|---------| |
A----B----C----D----C
|---------|
Figure 3
|---------|---------|
A----B----D----A----C
|--------------|
Figure 4
Figures 2 thru 4 are typical examples of how 3 Kempe chains might force a
4-coloring on Figure 1. There is one more possible configuration; ie
|--------------|
|---------| |
A----B----C----D----B
|--------------|
Figure 5
In Figure 5 one of the chains terminates on the same color; ie B. If this chain
is B-A-B, then it can cross the A-C and the A-D chains at a common A vertex.
Let's pretend that Figure 5 is a legitimate configuration and apply this coloring
to Figure 1b.
A B C
1--2--3
| / |
|/ |
B 5-----4 D
Figure 6
The 3 chains in Figure 5 are each external to Figure 1b. So it is possible to
draw an edge inside Figure 1b between v_2 and v_5. See Figure 6. With the
added edge, Figure 6 is not properly colored. If Figure 6 is not properly
4-colored, then G' is not properly 4-colored. If G' cannot be properly
4-colored, then Chi(G') > 4. Then G cannot be an mce because G' is not
4-colorable and G' is smaller than G.
If G' is 4-colorable, then G' is also 3-colorable. If G' is 3-colorable, then
G is 4-colorable. Again G cannot be an mce!
If three Kempe chains doesn't work, how about four?
But Figure 6 cannot be 4-colored because of the
B-A-B chain between v_2 & v_5!
The task of 4-colori
ng Figure 1 has been simplified by assigning arbitrary and
unchangeable colors to vertices v_1 thru v_4. These colors are fixed by Kempe
chains between v_1 & v_3 and between v_3 & v_4. The task is to force v_5 to
be color D [a 4th color] without disturbing either of these two chains?
Caveat: A 4-coloring means that it is impossible to properly 3-color the graph.
It does not mean a 4-coloring of a 3-colorable graph!
V_5 must be D if and only if it has A, B & C neighbors. Its B & C neighbors are shown.
Neighbor A is presumed as shown in Figure 2
3 C
|
5 D---A---X---A---X---A- ...
| 6 7 8 9 1
4 B 0
Figure 2
In Figure 2, Set 6 can be a single vertex. Set 7 contains all the vertices that
are neighbors of set 7. Set 8 means that all of the vertices in Set 7 have an
A neighbor. Sets 9 and 10 insure that set 9 has A colored vetices.
Generally the even-numbered sets have only A vertices and the odd-numered sets have
B, C & D vertices, but may never have an A's
The point here is that the chain as it were, is not self terminating. Set 10
would not necssarily be all A's if Set 11 was not there to assure this.
Set 11 could have some A vertices if it were not for the A vetices in set 12, etc.
If the chain was toggled so that the odd-numbered vertices became A vertices,
then v_5 could be A!