Berge-Fulkerson conjecture --- the planar case

Question

A well-known conjecture of Berge and Fulkerson says that every bridgeless cubic graph has a collection of six perfect matchings that together cover every edge exactly twice. Is this still open for bridgeless cubic planar graphs?

Answer 1

The Berge-Fulkerson conjecture holds for planar graphs. Here is a proof.

Let $G$ be a bridgeless cubic planar graph. The dual graph $G^*$ is a triangulation. By the Four Colour Theorem, $G^*$ has a 4-colouring $c$. We will use $\mathbb{Z}_2 \times \mathbb{Z}_2$ as the set of colours for $c$. Now for each edge $e \in E(G)$, colour $e$ with colour $c'(e):=c(f_1)+c(f_2)$ where $f_1$ and $f_2$ are the two faces of $G$ incident to $e$. Since $c$ is a proper colouring of $G^*$, $c'(e)$ is a non-zero element of $\mathbb{Z}_2 \times \mathbb{Z}_2$ for all $e \in E(G)$. Moreover, if $v \in V(G)$ and $e_1, e_2$, and $e_3$ are the edges of $G$ incident to $v$, then the dual edges $e_1^*, e_2^*$, and $e_3^*$ are a triangular face $\Delta$ in $G^*$. Since the vertices of $\Delta$ receive different colours in $c$, $c'(e_1), c'(e_2)$, and $c'(e_3)$ are all distinct. That is, $c'$ is a proper 3-edge colouring of $G$. In other words, $E(G)$ can be partitioned into three perfect matchings. So you can just use each of these perfect matchings twice.