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?



Berge-Fulkerson conjecture --- the planar case
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.


