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