DefIne G as a simple, loopless, triangulated planar graph; ie, a T-graph.
QUESTION: Is G a minimum counter example (MCE) to the Four Color Theorem?
To answer this question we need to know more about G. We know that every vertex
in G must have degree 5 or greater. We assume that G is not 4-colorable. We
know that if we remove any vertex from G and triangulate the resulting graph;
the triangulation will be 4-colorable!
6 7
/ \ P / \ \ | /
A / B \ / C \ D A---B-P-C---D
-------1-----2-----3------ | | | |
|\ | /| | | | |
| \ E | F / | | E---F |
| \ | / | | | | |
| \ | / | | | | |
| \|/ | | | | |
G | H 0 I | J G---H I---J
| / \ | | | | |
| / \ | | | | |
| / \ | | \ / |
| / K \ | | K |
|/ \| | | |
--------5-----------4-------- | | |
| | | | |
L | M | N --- L-----M-----N---
| |
Figure 1.a Figure 1.b
Figure 1.a is the induced subgraph of G in the vicinity of the vertex; ie, 0
to be removed. G will always have at least one vertex with exactly degree = 5.
The maximum number of edges in a T-graph is 3*V - 6. The sum of the degrees for
all V vertices is 6*V - 12. The average degree per vertex is 6 - 12/V.
Therefore, if every vertex has 5+ degree and the average degree is < 5, then
one or more vertices must have degree = 5.
Figure 2.a shows the pertinent subgraph of H; ie the triangulation after
vertex 0 has been removed from G.
6 7
/ \ O / \ \ | /
A / B \ / C \ D A---B-O-C---D
-------1-----2-----3------ | | | |
| / \ | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
G | E | | F | J G---E F---J
| | | | | | | |
| / \ | | | | |
| / \ | | \ / |
| / K \ | | K |
|/ \| | | |
--------5-----------4-------- | | |
| | | | |
L | M | N --- L-----M-----N---
| |
Figure 2.a Figure 2.b
Graph G and H are both T-graphs. Their face-to-vertex duals are both cubic
planar graphs (CPG). Figures 1.b and 2.b show the CPG duals for G and H
respectively. Let C_g be the dual of G and C_h be the dual of H.
It is known that if the dual is 4-face colorable, then the T-graph is
4-vertex colorable. The dual is known to be 4-face colorable if if it is
3-edge colorable. The dual is known to be 3-edge colorable, if it has a
Hamiltonian Circuit.
Unfortunately, the inability to 3-color the edges does not impact upon
4-face colorability!
Figures 2.a and Figure 2.b show the pertinent subgraph of (G_v) and the attendant
cubic dual.
F G F G
1----2----3 1| |1
| A / \ B | A B
| / \ | 2/3 \/2\3
J | / C \ | H J C H
|/ \| |
5---------4 |1
I I
Figure 2.a Figure 2.b