To follow on
[How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?
The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.
I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows
1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph
2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph
The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).
Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof.
The implication 4CT $\Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy.
The other implication is the one missing :
$$ \{ \forall G, \text{ cubic, planar, bridgeless}, \exists \text{ a 3-edge coloring}\}$$
$$\Rightarrow$$
$$\{\forall G, \text{ planar,} \ \exists \text{a 4-vertex-coloring}\}$$
Best Answer
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.