On two consequences of Berge–Fulkerson conjecture

Abstract

The classical Berge–Fulkerson conjecture states that any bridgeless cubic graph $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph $G$, edge $e$ and $i$ with $0\le i\le 2$, there are three perfect matchings $F_1,F_2,F_3$ of $G$ such that $F_1\cap F_2\cap F_3=0̸$ and $e$ belongs to exactly $i$ of these perfect matchings. The second one states that for any bridgeless cubic graph $G$ and its vertex $v$, there are three perfect matchings $F_1,F_2,F_3$ of $G$ such that $F_1\cap F_2\cap F_3=0̸$ and the edges incident to $v$ belong to $k_1$, $k_2$ and $k_3$ of these perfect matchings, where the numbers $k_1$, $k_2$ and $k_3$ satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph.

Keywords:

• Cubic graph
• Perfect matching
• Berge–Fulkerson conjecture
• Fan–Raspaud conjecture

1 The main result

In this paper, we consider graphs that may contain parallel edges, but no loops. A matching in a graph is a subset of edges such that no vertex is incident to two edges from the subset. A matching is perfect if any vertex is incident to exactly one edge from the matching. For a bridgeless cubic graph $G$, and a list of (not necessarily distinct) perfect matchings $C=(F_1,\dots ,F_k)$, let ${\nu }_C\left(e\right)$ be the number of perfect matchings of $C$ that contain the edge $e$. For non-defined concepts we refer to [1]. The main topics of this short note are the following two classical conjectures:

Conjecture 1

Berge, Unpublished Let $G$ be a bridgeless cubic graph. Then there is a list $C=(F_1,\dots ,F_5)$ of perfect matchings, such that ${\nu }_C\left(e\right)\ge 1$ for any edge $e$ of $G$.

Conjecture 2

Berge–Fulkerson [2] Let $G$ be a bridgeless cubic graph. Then there is a list $C=(F_1,\dots ,F_6)$ of perfect matchings, such that ${\nu }_C\left(e\right)=2$ for any edge $e$ of $G$.

Clearly, Conjecture 2 implies Conjecture 1. In [3], it is shown that Conjecture 1 implies Conjecture 2. Thus the two conjectures are equivalent. A list $C=(F_1,F_2,F_3)$ of a bridgeless cubic graph $G$ is called an FR-triple, if $F_1\cap F_2\cap F_3=0̸$. The classical Fan–Raspaud conjecture asserts:

Conjecture 3

Fan–Raspaud [4] Any bridgeless cubic graph admits an FR-triple.

In this paper, we consider the following two conjectures:

Conjecture 4

For any bridgeless cubic graph $G$, any edge $e\in E\left(G\right)$ and$i\in \{0,1,2\}$, there is an FR-triple $C$ of $G$, such that ${\nu }_C\left(e\right)=i$.

Conjecture 5

Let $G$ be a bridgeless cubic graph, $e$,$f$ and$g$ be edges incident to the same vertex $v$ of $G$,$0\le i,j,k\le 2$ be three numbers with $i+j+k=3$. Then$G$ contains an FR-triple $C$, such that ${\nu }_C\left(e\right)=i$,${\nu }_C\left(f\right)=j$ and${\nu }_C\left(g\right)=k$.

It is easy to see that Conjecture 2 implies Conjecture 5, Conjecture 5 implies Conjecture 4, and Conjecture 4 implies Conjecture 3. We are ready to obtain our first result.

Theorem 1

Conjecture 4 is equivalent to Fan–Raspaud conjecture (Conjecture 3).

Proof

It suffices to show that Conjecture 3 implies Conjecture 4. Let $G$, its edge $e$ and $0\le i\le 2$ be given. Take one copy of Petersen graph $P$, 15 copies $G_1,\dots ,G_{15}$ of $G$, and let $e_1,\dots ,e_{15}$ be the copies of $e$ in these 15 graphs. Consider a bridgeless cubic graph $H$ obtained as follows: for $j=1,\dots ,15$ remove $j$th edge from $P$ and connect it with a $2$-edge-cut to $G_j-e_j$.

Now, by Conjecture 3 $H$ admits an FR-triple $C_H$. Observe that $C_H$ gives rise to an FR-triple $C_P$ of $P$. Let us show that there is an edge $f$ of $P$ such that ${\nu }_{C_P}\left(f\right)=i$. If $i=0$, then since the three perfect matchings of $C_P$ do not cover the Petersen graph, we can find an edge $f$ of $P$ lying outside their union. If $i=1$, then any perfect matching of $C_P$ has three edges that do not belong to the other two perfect matchings of $C_P$, thus $f$ can be any of these three edges. Finally, if $i=2$, then any perfect matching of $C_P$ has two edges that belong to exactly one of the other two perfect matchings of $C_P$, thus $f$ can be any of these two edges. In order to complete the proof, consider the FR-triple of $G$ corresponding to the copy $f$ arising from $C_H$. Observe that in this FR-triple $e$ belongs to exactly $i$ of the perfect matchings. The proof is complete. □

Our next result deals with the smallest counter-example to Conjecture 5.

Theorem 2

The smallest counter-example to Conjecture 5 is cyclically$4$-edge-connected.

Proof

Let $G$ be a smallest counter-example to Conjecture 5. Clearly, it is connected. Let us show that it has no $2$-edge-cuts. On the opposite assumption, consider a $2$-edge-cut $J$. Let us show that $J\cap \{e,f,g\}\ne 0̸$. If none of $e$, $f$ and $g$ is in $J$, then consider the standard two smaller graphs $G_1$ and $G_2$, that is, the two components of $G-J$, where two degree-two vertices in the same component are joined with a new edge. Assume that $G_1$ contains the vertex $v$. Then since $G_1$ is smaller than $G$, it has an FR-triple containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. Let $l$ be the frequency of the new edge of $G_1$ arising from $J$. Now, we can take a similar FR-triple in $G_2$, where the new edge of $G_2$ is covered exactly $l$ times, and if we glue these two FR-triples, we will have an FR-triple of $G$ containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. This is a contradiction.

Now, assume that $e\in J$. Clearly $f,g\notin J$. Again assume that $G_1$ contains the vertex $v$. Since $G_1$ is smaller, we have that it admits an FR-triple containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. Now, take an FR-triple containing the new edge of $G_2$ $i$ times. If we glue these FR-triples, we will have an FR-triple in $G$ containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. This is a contradiction.

Thus, we have that $G$ is $3$-edge-connected. Now, let us show that all $3$-edge-cuts of $G$ are trivial. Assume that $G$ contains a non-trivial $3$-edge-cut $J$. Let us show that $J\cap \{e,f,g\}\ne 0̸$. If none of $e$, $f$ and $g$ is in $J$, then consider the standard two smaller graphs $G_1$ and $G_2$, that is, $G_1$ and $G_2$ are obtained by contracting the two shores of $J$ to a vertex, respectively. Assume that $G_1$ contains the vertex $v$. Then since $G_1$ is smaller than $G$, it has an FR-triple containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. Let the frequency of edges of $J$ in this FR-triple of $G_1$ be $l_1,l_2,l_3$. Clearly, $l_1+l_2+l_3=3$ and $0\le l_1,l_2,l_3\le 2$. Now, since $G_2$ is not a counter-example, we can find an FR-triple in $G_2$ such that the three edges of $J$ are covered $l_1$, $l_2$ and $l_3$ times. Now, if we glue back these two FR-triples, we will have an FR-triple of $G$ covering $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. This is a contradiction.

Thus, we are left with the case when $e\in J$. Observe that since $G$ is $3$-edge-connected, $J$ is a matching, hence $f,g\notin C$. Then since $G_1$ is smaller than $G$, it has an FR-triple containing $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. Let the frequency of edges of $J$ in this FR-triple of $G_1$ be $l_1,l_2,l_3$. Clearly, $l_1+l_2+l_3=3$ and $0\le l_1,l_2,l_3\le 2$. Now, since $G_2$ is not a counter-example, we can find an FR-triple in $G_2$ such that the three edges of $J$ are covered $l_1$, $l_2$ and $l_3$ times. Now, if we glue back these two FR-triples, we will have an FR-triple of $G$ covering $e$, $f$ and $g$, $i$, $j$ and $k$ times, respectively. This is a contradiction.

Thus, all $3$-edge-cuts of $G$ have to be trivial, which means that $G$ is cyclically $4$-edge-connected. The proof is complete. □

Let us note that it is unknown whether the smallest counter-example to Fan–Raspaud conjecture is cyclically $4$-edge-connected or even $3$-edge-connected. On the other hand, it can be shown that the smallest counter-example to Conjecture 4 is $3$-edge-connected. It would be interesting to show that Conjecture 5 is equivalent to Conjecture 3.¹

Notes

1 Recently, G. Mazzuoccolo and J.P. Zerafa showed that Conjecture 5 is equivalent to Conjecture 3. Their proof relies on Theorem 1.