Return to Answer

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 near-triangulation (every face except the outerface is a triangle). 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.

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.

Yes, 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 near-triangulation (every face except the outerface is a triangle). 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.

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 near-triangulation (every face except the outerface is a triangle). 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.

Yes, the Berge-Fulkerson conjecture holds for planar graphs. In fact, by the Four Colour Theorem, the edges of every bridgeless cubic planar graph can be partitioned into three perfect matchings. So you can just use each of these perfect matchings twice.

Yes, 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 near-triangulation (every face except the outerface is a triangle). 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.