minimal counter-example to the 4CT.
To understand why this is true, we must understand the mce/4CT. The mce/4CT
involves two similiar but slightly different graphs; ie, G a simple loopless
maximal planar graph and H a simple loopless planar graph. H is an induced
subgraph of G.
1. If G is an mce, then Chi(G) > 4 and Chi(H) < 5.
Consider Figure 1
1--2--3 1--2--3
|\ | /| | |
| \|/ | | |
| 0 | | |
| / \ | | |
|/ \| | |
5-----4 5-----4
Figure 1a Figure 1b
Figure 1a is an induced subgraph of G; Figure 1B is an induced subgraph of H
Statement 1 above is true, only when Figure 1b has a 4-coloring.
In Figure 6 an arbitrary coloring has been assigned to Figure 1b.
A B C
1--2--3
| / |
|/ |
B 5-----4 D
Figure 6
Note the edge between v_2 & v_5. This edge can be added because H is not
maximal; and v_2 & v_5 are the same color. Since no vertices were added,
H is still smaller than G.
Figure 6 is not properly 4-colored. Therefore graph H is not properly 4-colored!
Can Figure 6 be properly 4-colored without exposing a flaw in the original
coloring? Example: Figure 6 can be made 4-colorable by changing v_2 to D or
v_5 to C. It is possible that both of the changes can be made simultaneously!
If so, then Figure 6 can be properly 3-colored. There is a flaw in the original
coloring, and G is not an mce!
If Figure 6 cannot be properly 4-colored [or 3-colored], then G is not an mce
because it is not minimal!
The basis of a proof is to prove that Figure 6 may either be 3-colorable or
5-colorable; but never 4-colorable!
Let's look at Figure 6 in more details.
|.................| Internal chord {25}
|-----------------| External {B-A-B} Kempe Chain
A-----B-----C-----D-----B
|-----------| | External {A-C} Kempe Chain
|-----------------| External {A-D} Kempe Chain
Figure 7
Figure 7 is an attempt to show how a 4-coloring might be forced on Figure 6.
The external {B-A-B} chain is the key. The {B-A-B} chain is valid as it
can cross the {A-C} and {A-D} chains at common A vertices.