We know that the 4CT is true:
1. If certain 3-regular maps (cubic planar graphs) are 4 face colorable
2. If all simple loopless triangulations are 4 vertex colorable.
a. All vertices of the triangulation must be of degree = 5.
The triangulations of 2. must be face-vertex duals of the maps/graphs of 1.
The certain maps/graphs of 1. are the face-vertex duals of the triangulations in 2.
For simplicity, let G be a typical triangulation as defined in 2 and 2.a above.
Let C be the cubic planar graph that is the dual of G. Then G is the dual of C
C will have no cycles with fewer than 5 vertices. All cubics of type 1 are
triangle-free
C will have no bridges. If C has a bridge, then its dual has a looped vertex and
parallel edges.
C must be planar. If C is non-planar, then its dual cannot be a type 2 triangulation
If C is 3 edge colorable, then C is 4 face colorable.
If C is hamiltonian, then C is 3 edge colorable.
IS THIS GRAPH THREE EDGE COLORABLE?
A A 4
|----------------------------------| B 8
| \ B / | C 5
| |--|--------|-----|-------|--| | D 5
| | | | C | | | | E 5
| | | D |--|--| E | | | F 5
| | | / | \ | | | G 5
| |F |-----| G | H |-----| I| | H 5
| | | \ | / | | | I 5
| | | |--|--| | | | J 5
| | | | J | | | | K 5
|K |--| L |-----| M |--| N| L 8
| | | | O | | | | M 8
| | | |--|--| | | | N 5
| | | / | \ | | | O 5
| |P |-----| Q | R |-----| S| | P 5
| | | \ | / | | | Q 5
| | | T |--|--| U | | | R 5
| | | | V | | | | S 5
| |--|--------|-----|-------|--| | T 5
| / W \ | U 5
|----------------------------------| V 5
W 8