7
$\begingroup$

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?

$\endgroup$

1 Answer 1

12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.