4 color theorem equivalent to cubic planar bridgeless are 3 edge colorable

Question

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}\}$$

Answer 1

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.

Answer 2

Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.

About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.

The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.

UPDATE (25/Jan/2019): The proof should be here:

• P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society of Edinburgh Section A, 10: 501-503, 1878-1880.
  • https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0