4
$\begingroup$

How can be proved, that

The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.

I can't figure out or find any prove of this theorem.

Thanks.

$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

The two problems of three-edge-coloring and four-face-coloring for the same map are equivalent.

A proof of this equivalency can be round here: http://www.mathpuzzle.com/4Dec2001.htm. Search for "material added 19 November 2001" within the page.

Since the four color problem has been already proved, also the three edge coloring is true.

$\endgroup$
3
  • 1
    $\begingroup$ 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 edge-coloring, gow to build a 4 face coloring. The theorem by Tait is much more powerful. If I can 3-ege color any cubic bridgeless planar graph than I can 4-color ANY planar graph (not just cubic bridgeless). $\endgroup$
    – Thomas Lesgourgues
    Jan 7, 2019 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – Mario Stefanutti
    Jan 24, 2019 at 2:12
  • $\begingroup$ No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. Tait's theorem is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$. $\endgroup$
    – Thomas Lesgourgues
    Jan 24, 2019 at 9:11
2
$\begingroup$

The four colors can be represented by bit-vectors of length 2.

We can define $3$ transformations, $L, R, B$ on these bit-vectors, where $L$ inverts the left-bit, $R$ inverts the right-bit, and $B$ inverts both bits. Each of these is bijective with no fixed point.

Note that composing all three of these gives the identity, and composing any two of them gives the third.

Now consider a maximal planar graph. If the vertices can be $4$-colored then each edge determines one of these transformations and the edges of a triangle must have all $3$ transformations in order to compose to the identity transformation.

Conversely, if the edges can be $3$-colored such that the $3$ edges of each triangle have different colors, then $L,R,B$ can be used for the colors, and the transformations can be used to extend a color on a starting vertex to the whole graph.

$\endgroup$
1
$\begingroup$

I'd wondered about this before, but never worked it out until now. If $G$ is a cubic bridge-less graph, it is polyhedral and its dual is a maximal planar graph. Consider a maximal planar dual, $D(G)$ colored by the colors $(a, b, c, d$). Now color each edge, $e_{ij}$, according to $(i,j)$ like so:

$$(a, b) \equiv (c,d) \equiv 1$$ $$(a, c) \equiv (b,d) \equiv 2$$ $$(a, d) \equiv (b,c) \equiv 3$$

In each triangle, no two edges can possible have the same color, because that require all four vertex colors. Thus, in $G$, the edges all have different colors around every vertex. Since the edge coloring is valid around every vertex, it is valid for the whole graph $G$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .