ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 87-103
https://doi.org/10.26493/1855-3974.1860.a3d
(Also available at http://amc-journal.eu)
An equivalent formulation of the Fan-Raspaud Conjecture and related problems
Dipartimento di Informatica, Universita di Verona, Strada Le Grazie 15, Verona, Italy
Jean Paul Zerafa ©
Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Universita di Modena e Reggio Emilia, Via Campi 213/B, Modena, Italy
Received 20 November 2018, accepted 17 December 2019, published online 7 July 2020
In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges.
Keywords: Cubic graph, perfect matching, oddness, Fan-Raspaud Conjecture, Berge-Fulkerson Conjecture, Petersen-colouring. Math. Subj. Class. (2020): 05C15, 05C70
1 Introduction and terminology
Many interesting problems in graph theory are about the behaviour of perfect matchings in cubic graphs. One of the early classical results was made by Petersen [28] and states that every bridgeless cubic graph has at least one perfect matching. Some years ago, one of the most prominent conjectures in this area was completely solved by Esperet et al. in [5]: the conjecture, proposed by Lovisz and Plummer in the 1970s, stated that the number
E-mail addresses: giuseppe.mazzuoccolo@univr.it (Giuseppe Mazzuoccolo), jeanpaul.zerafa@unimore.it (Jean Paul Zerafa)
Giuseppe Mazzuoccolo ©
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
106
Ars Math. Contemp. 18 (2020) 105-115
of perfect matchings in a bridgeless cubic graph grows exponentially with its order (see
[20]).	However, many others are still open, such as Conjecture 2.1 proposed independently by Berge and Fulkerson in the 1970s as well, and Conjecture 2.2 by Fan and Raspaud (see [10] and [7], respectively). These two conjectures are related to the behaviour of the union and intersection of sets of perfect matchings, and properties of this kind are already largely studied: see, amongst others, [1, 2, 15, 16, 17, 19, 22, 23, 25, 30, 31]. In this paper we prove that a seemingly stronger version of the Fan-Raspaud Conjecture is equivalent to the classical formulation (Theorem 3.3), and so to another interesting formulation proposed in
[21]	(see also [18]). In the second part of the paper (Section 4 and Section 5), we study a weaker conjecture proposed by the first author in [24]: we show how we can state it in terms of a variant of Petersen-colourings (Proposition 4.1) and we prove it for cubic graphs of oddness four (Theorem 5.4). Although all mentioned conjectures are about simple cubic graphs without bridges, we extend our study of the union of two perfect matchings to bridgeless cubic multigraphs and to particular cubic graphs having bridges (Section 6.1 and Section 6.2).
Graphs considered in the sequel, unless otherwise stated, are simple connected bridge-less cubic graphs and so do not contain loops and parallel edges. Graphs that may contain parallel edges will be referred to as multigraphs. For a graph G, let V(G) and E(G) be the set of vertices and the set of edges of G, respectively. A matching of G is a subset of E(G) such that any two of its edges do not share a common vertex. For an integer k > 0, a k-factor of G is a spanning subgraph of G (not necessarily connected) such that the degree of every vertex is k. The edge-set of a 1-factor is said to be a perfect matching. The least number of odd cycles amongst all 2-factors of G, denoted by w(G), is called the oddness of G, and is clearly even for a cubic graph since G has an even number of vertices. For M C E(G), we denote the graph G\ M by M. In particular, when M is a perfect matching of G, then M is a 2-factor of G. In this case, following the terminology used for instance in [8], if M has w(G) odd cycles, then M is said to be a minimal perfect matching.
A cut in G is any set X C E(G) such that X has more components than G, and no proper subset of X has this property, i.e. for any X' c X, X' does not have more components than G. The set of edges with precisely one end in W C V(G) is denoted by dGW, or just dW when it is obvious to which graph we are referring. Moreover, a cut X is said to be odd if there exists a subset W of V(G) having odd cardinality such that X = dW.
We next define some standard operations on graphs that will be useful in the sequel. Let Gi and G2 be two bridgeless graphs (not necessarily cubic), and let e1 and e2 be two edges such that e1 = u1v1 G E(G1) and e2 = u2v2 G E(G2). A 2-cut connection on u1v1 and u2v2 is a graph operation that consists of constructing the new graph
[G1 - e1] U [G2 - e2] U {«1^2, V1V2},
and denoted by G1(u1v1) * G2(u2v2). It is clear that another possible graph obtained by a 2-cut connection on e1 and e2 is G1(u1v1) * G2(v2u2). Clearly, the two graphs obtained are bridgeless, and, unless otherwise stated, if it is not important which of these two graphs is obtained, we use the notation G1(e1) * G2(e2) and we say that it is a graph obtained by a 2-cut connection on e1 and e2.
Now, let G1 and G2 be two bridgeless cubic graphs, v1 g V(G1) and v2 g V(G2) such that the vertices adjacent to v1 are x1, y1 and z1, and those adjacent to v2 are x2, y2 and z2. A 3-cut connection (sometimes also known as the star product, see for instance [11]) on v1
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101
and v2 is a graph operation that consists of constructing the new graph
[Gi - vi] U [G2 - V2] U {xix2, yiy2, Z1Z2},
and denoted by G1(x1y1z1)*G2(x2y2z2). The 3-edge-cut {x1x2, y1y2, z1z2} is referred to as the principal 3-edge cut (see for instance [9]). As in the case of 2-cut connections, other graphs can be obtained by a 3-cut connection on v1 and v2, and, unless otherwise stated, if it is not important how the adjacencies in the principal 3-edge cut look like, we use the notation G1(v1) * G2(v2) and we say that it is a graph obtained by a 3-cut connection on v1 and v2. It is clear that any resulting graph is also bridgeless and cubic.
2 A list of relevant conjectures
One of the aims of this paper is to study the behaviour of perfect matchings in cubic graphs, more specifically the union of two perfect matchings (see Section 4 and Section 5). We relate this to well-known conjectures stated here below, in particular: the Berge-Fulkerson Conjecture and the Fan-Raspaud Conjecture.
Conjecture 2.1 (Berge-Fulkerson [10]). Every bridgeless cubic graph G admits six perfect matchings M1,..., M6 such that any edge of G belongs to exactly two of them.
Berge-Fulkerson Conjecture

Fan-Raspaud Conjecture

Conjecture 2.3
Prop. 2.5
f \ Conjecture 2.4
L_J
Figure 1: Conjectures mentioned and how they are related.
We also state here other (possibly weaker) conjectures implied by the above conjecture.
Conjecture 2.2 (Fan-Raspaud [7]). Every bridgeless cubic graph admits three perfect matchings M1,M2, and M3 such that M1 n M2 n M3 = 0.
In the sequel we will refer to three perfect matchings satisfying Conjecture 2.2 as an FR-triple. We can see that Conjecture 2.2 is immediately implied by the Berge-Fulkerson Conjecture, since we can take any three perfect matchings out of the six which satisfy Conjecture 2.1. A still weaker statement implied by the Fan-Raspaud Conjecture is the following:
Conjecture 2.3 ([21]). For each bridgeless cubic graph G, there exist two perfect matchings M1 and M2 such that M1 n M2 contains no odd-cut of G.
We claim that any two perfect matchings out of the three in an FR-triple have no odd-cut in their intersection, in other words that Conjecture 2.2 implies Conjecture 2.3. For, suppose not. Then, without loss of generality, suppose that M2 n M3 contains an odd-cut X. Hence, since every perfect matching has to intersect an odd-cut at least once, |M1 n (M2 n M3)| > |M1 nX| > 1, a contradiction, since we assumed that M1 n M2 n M3 is empty. In relation to the above, the first author proposed the following conjecture:
Conjecture 2.4 (S4-Conjecture [24]). For any bridgeless cubic graph G, there exist two perfect matchings such that the deletion of their union leaves a bipartite subgraph of G.
106
Ars Math. Contemp. 18 (2020) 105-115
For reasons which shall be obvious in Section 4 we let such a pair of perfect matchings be called an S4-pair of G and shall refer to Conjecture 2.4 as the S4-Conjecture. We will first proceed by showing that this conjecture is implied by Conjecture 2.3, and so, by what we have said so far, is a consequence of the Berge-Fulkerson Conjecture. In particular, we can see the S4-Conjecture as Conjecture 2.3 restricted to odd-cuts dV(C), where C is an odd cycle of G.
Proposition 2.5. Conjecture 2.3 implies the S4-Conjecture.
Proof. Let M1 and M2 be two perfect matchings such that their intersection does not contain any odd-cut. Consider M1 U M2, and suppose that it contains an odd cycle C. Then, all the edges of dV(C) belong to Mi n M2. If dV(C) has exactly two components, then dV(C) is an odd-cut belonging to M1 n M2, a contradiction. Therefore, dV(C) must have more than two components, say k, denoted by C1, C2,..., Ck, where the first component C1 is the cycle C. Let [C1, Cj] denote the set of edges between C1 and Cj, for j e {2,..., k}. Since £k=2 |[C1, Cj]| = |dV(C)| = 1 (mod 2), there exists j' e {2,..., k}, such that |[C1,Cj/]| = 1 (mod 2). However, [C1,Cj/] is an odd-cut which belongs to M1 n M2, a contradiction.	□
3 Statements equivalent to the Fan-Raspaud Conjecture
Let M1,..., Mt be a list of perfect matchings of G, and let a e E(G). We denote the number of times a occurs in this list by vG[a : M1,..., Mt]. When it is obvious which list of perfect matchings or which graph we are referring to, we will denote this as v(a) and refer to it as the frequency of a. We will sometimes need to refer to the frequency of an ordered list of edges, say (a, b, c), and we will do this by saying that the frequency of (a, b, c) is (i, j, k), for some integers i, j and k. Mkrtchyan et al. [27] showed that the Fan-Raspaud Conjecture, i.e. Conjecture 2.2, is equivalent to the following:
Conjecture 3.1 ([27]). For each bridgeless cubic graph G, any edge a e E(G) and any i e {0,1, 2}, there exist three perfect matchings M1, M2, and M3 such that M1 n M2 n M3 = 0 and vG[a : M1,M2,M3] = i.
In other words they show that if a graph has an FR-triple then, for every i in {0,1,2}, there exists an FR-triple in which the frequency of a pre-chosen edge is exactly i. In the same paper, Mkrtchyan et al. state the following seemingly stronger version of the Fan-Raspaud Conjecture:
Conjecture 3.2 ([27]). Let G be a bridgeless cubic graph, w a vertex of G and i, j and k three integers in {0,1,2} such that i + j + k = 3. Then, G has an FR-triple in which the edges incident to w in a given order have frequencies (i, j, k).
This means that we can prescribe the frequencies to the three edges incident to a given vertex. At the end of [27], the authors remark that it would be interesting to show that Conjecture 3.2 is equivalent to the Fan-Raspaud Conjecture. We prove here that this is actually the case.
Theorem 3.3. Conjecture 3.2 is equivalent to the Fan-Raspaud Conjecture.
Proof. Since the Fan-Raspaud Conjecture is equivalent to Conjecture 3.1, it suffices to show the equivalence of Conjectures 3.1 and 3.2. The latter clearly implies the former, so
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101

assume Conjecture 3.1 is true and let a, b and c be the edges incident to w such that the frequencies (i, j, k) are to be assigned to (a, b, c). It is sufficient to show that there exist two FR-triples in which the frequencies of (a, b, c) are (2,1,0) in one FR-triple (Case 1 below) and (1,1,1) in the other FR-triple (Case 2 below).
Figure 2: The graphs K4 and K** in Case 1 of the proof of Theorem 3.3.
Case 1. Let ui, u3 and u4 be the vertices of the complete graph K4 as in Figure 2. Consider two copies of G, and let the vertex w in the ¿th copy of G be denoted by for each i e {1, 2}. We apply a 3-cut connection between u and wi; for each i € {1, 2}. With reference to this resulting graph, denoted by K**, we refer to the copy of the graph G - w at u1 as G1; and to the corresponding edges a, b and c as a1, b1 and c1, respectively. The graph G2 and the edges a2, b2 and c2 are defined in a similar way, and the 3-cut connection is done in such a way that b1 and b2 are adjacent, and also c1 and c2, as Figure 2 shows. Note also that a1 and a2 coincide in K|. By our assumption, there exists an FR-triple M1, M2 and M3 of K** in which the edge u3u4 has frequency 2. Without loss of generality, let u3u4 e M1 n M2. Then, a1 (and so a2) must belong to M1 n M2. Clearly, a1 (and so a2) cannot belong to M3, and so the principal 3-edge-cuts with respect to G1 and G2 do not belong to M3. If b1 e M3, then we are done, as then M1, M2 and M3 restricted to G1, together with a and b having the same frequencies as a1 and b1, induce an FR-triple of G such that the frequencies of (a, b, c) are (2,1,0). So suppose c1 e M3. Then, b2 e M3, and so by a similar argument applied to G2 and the corresponding edges, M1, M2 and M3 induce an FR-triple in G such that the frequencies of (a, b, c) are (2,1,0).
Figure 3: The graphs P and P* in Case 2 of the proof of Theorem 3.3.
Case 2. Let P be the Petersen graph and {u1, u2, u3, u4} be a maximum independent set of vertices in P as in Figure 3. Consider four copies of G. Let the vertex w in the ith copy of G be denoted by wj, for each i e {1,..., 4}. Let P* be the graph obtained by applying
U3 U4
106
Ars Math. Contemp. 18 (2020) 105-115
a 3-cut connection between each w and w», as shown in Figure 3. Similar to Case 1 we refer to the copy of G — w at w as G and to the corresponding edges a, b and c as a^ bj and cj, respectively. Since we are assuming that Conjecture 3.1 is true, we can consider an FR-triple Mi, M2 and M3 of P* in which the edge e incident to both ai and a4 has frequency 2. Without loss of generality, let the two perfect matchings containing e be Mi and M2. The edges a i, c2, c3 and a4 are not contained in Mi and neither M2, since they are all incident to e, and so no principal 3-edge-cut leaving G» belongs to Mi or M2. Then, Mi and M2 induce perfect matchings of P (clearly distinct), and since there are exactly two perfect matchings of P containing e, we can assume that Mi contains {e, bi, a2, a3, b4}, and M2 contains {e, ci, b2, b3, c4}.
If the third perfect matching M3 induces a perfect matching of the Petersen graph then the induced perfect matching cannot be one of the perfect matchings induced by Mi and M2 in P. Hence, since every two distinct perfect matchings of P intersect in exactly one edge of P, there exists i G {1, 2,3,4} such that the frequencies of (aj,bj,cj) are (1,1,1) and so, Mi, M2 and M3 restricted to Gj, together with a, b and c having the same frequencies as aj, bj and cj, induce an FR-triple in G with the needed property.
Therefore, suppose M3 contains the principal 3-edge-cut of one of the Gjs, say Gi by symmetry of P*. Thus, ai, bi and ci belong to M3. The perfect matching M3 can intersect the principal 3-edge-cut at G2 either in b2 or c2 (not both). If c2 G M3 we are done by the same reasoning above applied to G2 and the corresponding edges. So suppose b2 G M2 n M3. Then, c4 G M3, and M3 can only intersect the principal 3-edge-cut at G3 in c3, implying that the frequencies of (a3, b3, c3) are (1,1,1) in P* and that Mi, M2 and M3 restricted to G3, together with a, b and c having the same frequencies as a3, b3 and c3, induce an FR-triple in G with the needed property.	□
In [27] it is also shown that a minimal counterexample to Conjecture 3.2 is cyclically 4-edge-connected. It remains unknown whether a smallest counterexample to the original formulation of the Fan-Raspaud Conjecture has the same property. Indeed, we only prove that the two assertions are equivalent, but we cannot say whether a possible counterexample to Conjecture 3.2 is itself a counterexample to the original formulation.
4 Statements equivalent to the S4-Conjecture
All conjectures presented in Section 2 are implied by a conjecture made by Jaeger in the late 1980s. In order to state it we need the following definitions. Let G and H be two graphs. An H-colouring of G is a proper edge-colouring f of G with edges of H, such that for each vertex u g V(G), there exists a vertex v g V(H) with f (dG{u}) C dH{v}. If G admits an H-colouring, then we will write H -< G. In this paper we consider S4-colourings of bridgeless cubic graphs, where S4 is the multigraph shown in Figure 4.
Figure 4: The multigraph S4.
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101

The importance of H-colourings is mainly due to Jaeger's Conjecture [14] which states that each bridgeless cubic graph G admits a P-colouring (where P is again the Petersen graph). For recent results on P-colourings, known as Petersen-colourings, see for instance [12, 13, 26, 29]. The following proposition shows why we choose to refer to a pair of perfect matchings whose deletion leaves a bipartite subgraph as an S4-pair.
Proposition 4.1. Let G be a bridgeless cubic graph, then S4 -< G if and only if G has an S4-pair.
Proof. Along the entire proof we denote the edges of S4 by using the same labelling as in Figure 4. Let M1 and M2 be an S4-pair of G. The graph induced by Mi U M2, denoted by G[M1 U M2], is made up of even cycles and isolated edges, whilst the bipartite graph
M1 U M2 is made up of even cycles and paths. We obtain an S4-colouring of G as follows:
•	the isolated edges in M1 U M2 are given colour g0,
•	the edges of the even cycles in M1 U M2 are properly edge-coloured with g3 and g4, and
•	the edges of the paths and even cycles in M1 U M2 are properly edge-coloured with g1 and g2.
One can clearly see that this gives an S4-colouring of G. Conversely, assume that S4 -< G. We are required to show that there exists an S4 -pair of G. Let M1 be the set of edges of G coloured g3 and g0, and let M2 be the set of edges of G coloured g4 and g0. If e and f are edges of G coloured g3 (or g4) and g0, respectively, then e and f cannot be adjacent, otherwise we contradict the S4-colouring of G. Thus, M1 and M2 are matchings. Next, we show that they are in fact perfect matchings. This follows since for every vertex v of G, f (dG{v}) is equal to {01,03,04}, or {02,03,04}, or {00,01,02}. Thus, M1 U M2 is the graph induced by the edges coloured 01 and 02, which clearly cannot induce an odd cycle.	□
Hence, by the previous proof, Conjecture 2.4 can be stated in terms of S4-colourings, which clearly shows why we choose to refer to it as the S4-Conjecture. In analogy to what we did for FR-triples, here we prove that for S4-pairs we can prescribe the frequency of an edge and the frequencies of the edges leaving a vertex (the proof of the latter also implies that we can prescribe the frequencies of the edges of each 3-cut). Consider the following conjecture, analogous to Conjecture 3.1:
Conjecture 4.2. For any bridgeless cubic graph G, any edge a G E(G) and any i G {0,1,2}, there exists an S4-pair, say M1 and M2, such that vG[a : M1, M2] = i.
In Theorem 4.3 we show that the latter conjecture is actually equivalent to the S4-Conjecture. The proof given in [27] to show the equivalence of the Fan-Raspaud Conjecture and Conjecture 3.1 is very similar to the proof we give here for the analogous case for the S4-Conjecture, however, we need a slightly more complicated tool in our context.
Theorem 4.3. Conjecture 4.2 is equivalent to the S4-Conjecture.
Proof. Clearly, Conjecture 4.2 implies the S4-Conjecture so it suffices to show the converse. Assume the S4-Conjecture to be true and let f1, f2, f3 be three consecutive edges of K4 inducing a path. Consider two copies of G. Let the edge a in the ith copy of G
106
Ars Math. Contemp. 18 (2020) 105-115
be denoted by ai; for each i e {1,2}. Let K4 be the graph obtained by applying a 2-cut connection between f and ai for each i e {1,2}. We refer to the copy of the graph G - a on f as Gj.

Figure 5: An edge in P transformed into the corresponding structure in H.
Let {ei,..., e15} be the edges of the Petersen graph and let T1,..., T15 be fifteen copies of K4. For every i e {1,..., 15}, apply a 2-cut connection on ei and the edge f3 of Ti. Consequently, every edge ei of the Petersen graph is transformed into the structure Ei as in Figure 5, and we refer to G1 and G2 on Ei as G1 and G|, respectively. Let H be the resulting graph. By our assumption, there exists an S4-pair of H, say M1 and M2, which induces a pair of two distinct perfect matchings in P, say N1 and N2, respectively. There exists an edge of P, say ej, for some j e {1,..., 15}, such that vP [ej : N1, N2] = 1, since every two distinct perfect matchings of P have exactly one edge of P in common. Hence, the restriction of M1 and M2 to the edge set of G1, together with the edge a having the same frequency as ej, gives rise to an S4-pair of G in which the frequency of a is 1.
Moreover, there exists an edge of P, say ek, for some k e {1,..., 15}, such that vP [ek : N1, N2] = 2. Restricting M1 and M2 to the edge set of Gk, together with the edge a having the same frequency as ek, gives rise to an S4-pair of G, in which the frequency of a is 2. Also, the restriction of M1 and M2 to the edge set of Gf gives rise to an S4-pair of G (Gk together with a), in which the frequency of a is 0, because if not, then there exists an odd cycle in G, say of length a, passing through a and having all its edges with frequency 0. However, this would mean that there is an odd cycle of length a + 4 on Ek in M1 U M2 (in H), a contradiction.	□
As in Section 3, we state an analogous conjecture to Conjecture 3.2, but for S4-pairs:
Conjecture 4.4. Let G be a bridgeless cubic graph, w a vertex of G and i, j and k three integers in {0,1, 2} such that i + j + k = 2. Then, G has an S4-pair in which the edges incident to w in a given order have frequencies (i, j, k).
The following theorem shows that this conjecture is actually equivalent to Conjecture 4.2, and so to the S4-Conjecture by Theorem 4.3.
Theorem 4.5. Conjecture 4.4 is equivalent to the S4-Conjecture.
Proof. Since the S4-Conjecture is equivalent to Conjecture 4.2, it suffices to show the equivalence of Conjectures 4.2 and 4.4. Clearly, Conjecture 4.4 implies Conjecture 4.2 and so we only need to show the converse. Let a, b and c be the edges incident to w such that the frequencies (i, j, k) are to be assigned to (a, b, c). We only need to prove the case when (i, j, k) is equal to (1,1,0), as all other cases follow from Conjecture 4.2.
Consider the graph G(w) * P(v), where P is the Petersen graph and v is any vertex of P. We refer to the edges corresponding to a, b and c in G(w) * P(v), as aw, bw and cw.
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101

Figure 6: The graph G(w) * P(v) from Theorem 4.5.
Let d be an edge originally belonging to P and adjacent to cw in G(w) * P(v). Since we are assuming Conjecture 4.2 to be true, there exists an S4-pair in G(w) * P(v) in which d has frequency 2. If the frequencies of (aw, bw, cw) are (1,1,0), then we are done, because the S4-pair for G(w) * P(v) restricted to the edges in G - w, together with a and b having the same frequencies as aw and bw, give an S4-pair for G with the desired property. We claim that this must be the case. For, suppose not. Then, without loss of generality, the frequencies of (aw, bw, cw) are (2,0,0). This implies that all the edges of G(w) * P(v) originally in P have either frequency 0 or 2, since the two perfect matchings in the S4-pair induce the same perfect matching in P. However, this implies that P has a perfect matching whose complement is bipartite, a contradiction since P is not 3-edge-colourable. □
As in [27], a minimal counterexample to Conjecture 4.4 (but not necessarily to the S4-Conjecture) is cyclically 4-edge-connected. We omit the proof of this result as it is very similar to the proof of Theorem 2 in [27].
5 Further results on the S4-Conjecture
Little progress has been made on the Fan-Raspaud Conjecture so far. Bridgeless cubic graphs which trivially satisfy this conjecture are those which can be edge-covered by four perfect matchings. In this case, every three perfect matchings from a cover of this type form an FR-triple since every edge has frequency one or two with respect to this cover. Therefore, a possible counterexample to the Fan-Raspaud Conjecture should be searched for in the class of bridgeless cubic graphs whose edge-set cannot be covered by four perfect matchings, see for instance [6]. In 2009, Micajovi and Skoviera [22] shed some light on the Fan-Raspaud Conjecture by proving it for bridgeless cubic graphs having oddness two. One of the aims of this paper is to show that even if the S4-Conjecture is still open, some results are easier to extend than the corresponding ones for the Fan-Raspaud Conjecture. Clearly, the result by Micajovi and Skoviera in [22] implies the following result:
106
Ars Math. Contemp. 18 (2020) 105-115
Theorem 5.1. Let G be a bridgeless cubic graph ofoddness two. Then, G has an S4-pair.
We first give a proof of Theorem 5.1 in the same spirit of that used in [22], however much shorter since we are proving a weaker result.
Proof 1 of Theorem 5.1. Let M1 be a minimal perfect matching of G, and let C and C2 be the two odd cycles in M1. Colour the even cycles in M1 using two colours, say 1 and 2. For each i e {1, 2}, let Ej be the set of edges belonging to the even cycles in M1 and having colour i. In G, there must exist a path Q whose edges alternate in M1 and E1 and whose end-vertices belong to C1 and C2, respectively, since C1 and C2 are odd cycles. Note that since the edges of Ci and C2 are not edges in M1 U Ei, every other vertex on Q which is not an end-vertex does not belong to C1 and C2.
For each i e {1,2}, let vj be the end-vertex of Q belonging to C, and let MCi be the unique perfect matching of Cj - vj. Let M2 := (Mi n Q) U (Ei \ Q) U Mc1 U Mc2 . Clearly, M2 is a perfect matching of G which intersects C1 and C2, and so M1 U M2 is bipartite.	□
We now give a second alternative proof of the same theorem using fractional perfect matchings, which we will show to be easier to use for graphs having larger oddness. Let w be a vector in R|E(G)|. The entry of w corresponding to e e E(G) is denoted by w(e), and for A C E(G), we let the weight of A, denoted by w(A), to be equal to J2eeA w(e). The vector w is said to be a fractional perfect matching of G if:
1.	w(e) e [0,1] for each e e E(G),
2.	w(d{v}) = 1 for each v e V(G), and
3.	w(dW) > 1 for each W C V(G) of odd cardinality.
The following lemma is presented in [16] and it is a consequence of Edmonds' characterisation of perfect matching polytopes in [3].
Lemma 5.2. If w is a fractional perfect matching in a graph G, and c e R|E(G)|, then G has a perfect matching N such that
N ^
c • X > c • w,
where • denotes the inner product. Moreover, there exists a perfect matching satisfying the above inequality and which contains exactly one edge of each odd-cut X with w(X) = 1.
Remark 5.3. If we let w(e) = 1/3 for all e e E(G), for some graph G, then we know that w is a fractional perfect matching of G. Also, since the weight of every 3-cut is one, then by Lemma 5.2 there exists a perfect matching of G containing exactly one edge of each 3-cut of G.
Proof 2 of Theorem 5.1. Let M1 be a minimal perfect matching of G, and let C1 and C2 be the two odd cycles in M1. For each i e {1, 2}, let e1 and e2 be two adjacent edges belonging to Cj. We define the vector c e R|E(G)| such that
c(e) [1 if e eU?=1{e1,e2}, 10 otherwise.
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101
By Remark 5.3, we also know that if we let w(e) = Vs for all e G E(G), then w is a fractional perfect matching of G. Hence, by Lemma 5.2, there exists a perfect matching M2 such that c • xM2 > c • w, which implies that
I u2=i {el, e2} n M2| > i/s x 2 x 2 = 4/s > 1.
Therefore, for each i G {1,2}, there exists exactly one j G {1,2} such that ej G M2. Hence, M2 intersects C1 and C2 and so M1 U M2 is bipartite.	□
Using the same idea as in Proof 2 of Theorem 5.1, we also prove that the S4-Conjecture is true for graphs having oddness four.
Theorem 5.4. Let G be a bridgeless cubic graph of oddness four. Then, G has an S4-pair.
Proof. Let M1 be a minimal perfect matching of G, and let C1, C2, Cs and C4 be the four odd cycles in M1. By Remark 5.3, there exists a perfect matching N of G such that if G has any 3-cuts, then N intersects every 3-cut of G in one edge. Moreover, for every i G {1,..., 4}, there exists at least a pair of adjacent edges e1 and e| belonging to Q n N. We define the vector c g R|e(g)| such that
c(e) [1 if e GU4=1{e1,e2}, |0 otherwise.
We also define the vector w g R|e(g)| as follows:
.. J1/5 if e G N, w(e) =
2/5 otherwise.
The vector w is clearly a fractional perfect matching of G because, in particular, N intersects every 3-cut in one edge and so w(X) > 1 for each odd-cut X of G. Hence, by Lemma 5.2, there exists a perfect matching M2 such that c • xM2 > c • w, which implies that
| U4=1 {e1, e|} n M2| > 2/5 x 2 x 4 = 16/5 > 3. Therefore, for each i G {1,..., 4}, there exists exactly one j G {1,2} such that ej G M2. Hence, M2 intersects C1, C2, Cs and C4 and so M1 U M2 is bipartite.	□
As the above proofs show us, extending results with respect to the S4-Conjecture is easier than in the case of the Fan-Raspaud Conjecture and this is why we believe that a proof of the S4-conjecture could be a first feasible step towards a solution of the Fan-Raspaud Conjecture. For graphs having oddness at least six we are not able to prove the existence of an S4-pair and we wonder how many perfect matchings we need such that the complement of their union is bipartite. In the next proposition we use the technique used in Theorem 5.4 and show that given a bridgeless cubic graph G, if w(G) < 5k-1 - 1 for some positive integer k, then there exist k perfect matchings such that the complement of their union is bipartite. Note that for k = 2 we obtain w(G) < 4.
Proposition 5.5. Let G be a bridgeless cubic graph and let C be a collection of disjoint odd cycles in G such that |C| < 5k-1 — 1 for some positive integer k. Then, there exist k — 1 perfect matchings of G, say M1,..., Mk-1, such that for every C gC, there exists j G {1,..., k — 1} for which C n Mj = 0. Moreover, if w(G) < 5k-1 — 1, then there exist k perfect matchings such that the complement of their union is bipartite.
106
Ars Math. Contemp. 18 (2020) 105-115
Proof. We proceed by induction on k. For k = 1, the assertion trivially holds since C is the empty set. Assume the result is true for some k > 1 and consider k +1. Let Ci, C2,..., Ct, with t < 5k - 1, be the odd cycles of G in C. Let N be a perfect matching of G which intersects every 3-cut of G once. For every i e {1,..., t}, there exists at least a pair of adjacent edges e\ and e* belonging to C n N. We define the vector c e R|E(G)| such that
c(e) = /1 if e euLiRe*}, |0 otherwise.
We also define the vector w e R|E(G)| as follows:
.. J1/5 if e e N, w(e) =
2/5 otherwise.
As in the proof of Theorem 5.4, w is a fractional perfect matching of G and by Lemma 5.2 there exists a perfect matching Mk such that c • xMk > c • w. This implies that
| ut=1 {ei, e*} n Mk | > 2 x 2/5 x t.
Let C' be the subset of C which contains the odd cycles of C with no edge of Mk. Then, |C< |C| - 41 = t - 41 = 5 < 5k-i - 5, and so |C< 5k-i - 1. By induction, there exist k - 1 perfect matchings of G, say M1,..., Mk-1, having the required property with respect to C'. Therefore, M1,..., Mk intersect all odd cycles in C. The second part of the statement easily follows by considering C to be the set of odd cycles in the complement of a minimal perfect matching M of G, since the union of M with the k -1 perfect matchings which intersect all the odd cycles in C has a bipartite complement.	□
Remark 5.6. We note that with every step made in the proof of Proposition 5.5, one could update the weight w of the edges using the methods presented in [16, 23] which gives a slightly better upper bound for w(G). For reasons of simplicity and brevity, we prefer the present weaker version of Proposition 5.5.
6 Extension of the S4-Conjecture to larger classes of cubic graphs 6.1 Multigraphs
In this section we discuss natural extensions of some previous conjectures to bridgeless cubic multigraphs. We note that bridgeless cubic multigraphs cannot contain any loops. We will make use of the following standard operation on parallel edges, referred to as smoothing. Let G' be a bridgeless cubic multigraph. Let u and v be two vertices in G' such that there are exactly two parallel edges between them.
Figure 7: Vertices x, u, v and y in G'.
Let x and y be the vertices adjacent to u and v, respectively (see Figure 7). We say that we smooth uv if we delete the vertices u and v from G' and add an edge between x
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101

and y (even if x and y are already adjacent in G'). One can easily see that the resulting multigraph, say G, after smoothing uv is again bridgeless and cubic.
In what follows, we will say that a perfect matching M of G and a perfect matching M' of G' are corresponding perfect matchings if the following holds:
{M' U xy — {xu, vy} if xu G M', M' — uv	otherwise.
The following theorem can be easily proved by using smoothing operations.
Theorem 6.1. The S4-Conjecture is true if and only if every bridgeless cubic multigraph has an S4-pair.
Now we show that Conjecture 4.4 can also be extended to multigraphs.
Theorem 6.2. Let i, j and k be three integers in {0,1,2} such that i + j + k = 2 and let w be a vertex in a bridgeless cubic multigraph G'. Then, the S4-Conjecture is true if and
only if G' has an S4 -pair in which the edges incident to w in a given order have frequencies
(i j,k)
Proof. It suffices to assume that the S4-Conjecture is true and only show the forward direction, by Theorem 6.1. Let G' be a minimal counterexample and suppose it has some parallel edges. If G' = C2,3 then the result clearly follows. So assume G' = C2,3. Let a, b and c be the edges incident to w such that the frequencies (i, j, k) are to be assigned to (a, b, c). We proceed by considering two cases: when w has two parallel edges incident to it (Figure 8) and otherwise (Figure 9).
Figure 8: Case 1 in the proof of Theorem 6.2.
Case 1. Let G be the resulting multigraph after smoothing wv. By minimality of G', G has an S4-pair (say M1 and M2) in which v(xy) = k. It is easy to see that a pair of corresponding perfect matchings in G' give vG> (c) = vG> (vy) = k and can be chosen in such a way such that vG> (a) = i and vG> (b) = j, a contradiction to our initial assumption. Therefore, we must have Case 2.
a w c
a
y
b
b
Figure 9: Case 2 in the proof of Theorem 6.2.
Case 2. Let G be the resulting multigraph after smoothing some parallel edge in G' and let aw, bw and cw be the corresponding edges incident to w in G after smoothing is done.
106
Ars Math. Contemp. 18 (2020) 105-115
In G, there exists an S4-pair such that the frequencies of (aw, bw, cw) are equal to (i, j, k). Clearly, the corresponding perfect matchings in G' form an S4-pair in which the frequencies of (a, b, c) are (i, j, k), a contradiction, proving Theorem 6.2.	□
Using the same ideas as in Theorem 6.1 and Theorem 6.2 one can also state analogous results for the Fan-Raspaud Conjecture in terms of multigraphs.
6.2 Graphs having bridges
Since every perfect matching must intersect every bridge of a cubic graph, then the Fan-Raspaud Conjecture cannot be extended to cubic graphs containing bridges. The situation is quite different for the S4-Conjecture as Theorem 6.3 shows. By Errera's Theorem [4] we know that if all the bridges of a connected cubic graph lie on a single path, then the graph has a perfect matching. We use this idea to show that there can be graphs with bridges that can have an S4-pair.
Theorem 6.3. Let G be a connected cubic graph having k bridges, all of which lie on a single path, for some positive integer k. If the S4-Conjecture is true, then G admits an S4-pair.
Figure 10: G with k bridges lying all on the same path.
Proof. Let Bi, B2,..., Bfc+i be the 2-connected components of G and let ei,..., ek be the bridges of G such that ej = Wjvi+i for each i G {1,..., k}, where u G V(Bj) and vi+i G V(Bi+i). Let xi and yi be the two vertices adjacent to ui in Bi, and let xk+i and yk+i be the two vertices adjacent to vk+i in Bk+i. Let Bi = (Bi - ui) U xiyi and B'k+i = (Bfc+i - vk+i) U xfc+iyfc+i. Also, let Bj = Bj U vju for every i G {2,..., k}. Clearly, B',..., B'k +i are bridgeless cubic multigraphs. Since we are assuming that the S4-Conjecture holds, then, by Theorem 6.1, for every i G {1,..., k+1}, Bj has an S4-pair, say Mj and M2. Using Theorem 6.2, we choose the S4-pair in:
•	B', such that the two edges originally incident to xi (not xiui) both have frequency 1 ,
•	Bj, for each i g {2,..., k}, such that vB/ (vjUj) = 2, and
•	Bk+i, such that the two edges originally incident to xk+i (not xk+ivk+i) both have frequency 1 .
Let Mi := (Uk+Mj) U (Uk=iej) - Uik=2viui, and let M2 := (uk=+iiM2) U (Uk=iej) -uk=2v;u;. Then, Mi and M2 are an S4-pair of G.	□
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 101
Finally, we remark that there exist cubic graphs which admit a perfect matching however do not have an S4-pair. For example, since the edges WjVj in Figure 11 are bridges, then they must be in any perfect matching. Consequently, every pair of perfect matchings do not intersect the edges of the odd cycle T. This shows that it is not possible to extend the S4-Conjecture to the entire class of cubic graphs.
7 Remarks and problems
Many problems about the topics presented above remain unsolved: apart from asking if we can solve the Fan-Raspaud Conjecture and the S4-Conjecture completely, or at least partially for higher oddness, we do not know which are those graphs containing bridges which admit an S4-pair and we do not know either if the S4-Conjecture is equivalent to Conjecture 2.3. Here we would like to add some other specific open problems.
For a positive integer k, we define wk to be the largest integer such that any graph with oddness at most wk, admits k perfect matchings with a bipartite complement. Clearly, for k = 1, we have w1 = 0, since the existence of a perfect matching of G with a bipartite complement is equivalent to the 3-edge-colourability of G. Moreover, the S4-Conjecture is equivalent to wk = to, for k > 2, but a complete result to this is still elusive. Proposition 5.5 (see also Remark 5.6) gives a lower bound for wk and it would be interesting if this lower bound can be significantly improved. We believe that the following problem, weaker than the S4-Conjecture, is another possible step forward.
Problem 7.1. Prove the existence of a constant k such that every bridgeless cubic graph admits k perfect matchings whose union has a bipartite complement.
It is also known that not every perfect matching can be extended to an FR-triple and neither to a Berge-Fulkerson cover, where the latter is a collection of six perfect matchings which cover the edge set exactly twice. We do not see a way how to produce a similar argument for S4-pairs and so we also suggest the following problem.
Problem 7.2. Establish whether any perfect matching of a bridgeless cubic graph can be extended to an S4-pair.
Figure 11: A cubic graph with bridges having no S4-pair.
106
Ars Math. Contemp. 18 (2020) 105-115
It can be shown that Problem 7.2 is equivalent to saying that given any collection of disjoint odd cycles in a bridgeless cubic graph, then there exists a perfect matching which intersects all the odd cycles in this collection.
ORCID iDs
Giuseppe Mazzuoccolo © https://orcid.org/0000-0001-7775-065X Jean Paul Zerafa © https://orcid.org/0000-0002-3159-2980
References
[1]	M. Abreu, T. Kaiser, D. Labbate and G. Mazzuoccolo, Treelike snarks, Electron. J. Combin. 23
(2016),	#P3.54, doi:10.37236/6008.
[2]	A. Bonisoli and D. Cariolaro, Excessive factorizations of regular graphs, in: A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier and J. L. Ramirez Alfonsin (eds.), Graph Theory in Paris, Springer, Trends in Mathematics, pp. 73-84, 2007, doi:10.1007/978-3-7643-7400-6_7, proceedings of the conference (GTO4) in memory of Claude Berge held in Paris, July 2004.
[3]	J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur. Standards 69B (1965), 125-130, doi:10.6028/jres.069B.013.
[4]	A. Errera, Une démonstration du théorème de Petersen, Mathesis 36 (1922), 56-61.
[5]	L. Esperet, F. Kardos, A. D. King, D. Krâl and S. Norine, Exponentially many perfect match-ings in cubic graphs, Adv. Math. 227 (2011), 1646-1664, doi:10.1016/j.aim.2011.03.015.
[6]	L. Esperet and G. Mazzuoccolo, On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings, J. Graph Theory 77 (2014), 144-157, doi:10.1002/jgt.21778.
[7]	G. Fan and A. Raspaud, Fulkerson's conjecture and circuit covers, J. Comb. Theory Ser. B 61 (1994), 133-138, doi:10.1006/jctb.1994.1039.
[8]	M. A. Fiol, G. Mazzuoccolo and E. Steffen, Measures of edge-uncolorability of cubic graphs, Electron. J. Combin. 25 (2018), #P4.54, doi:10.37236/6848.
[9]	J.-L. Fouquet and J.-M. Vanherpe, On the perfect matching index of bridgeless cubic graphs, 2009, preprint, arXiv:0 904.12 96 [cs.DM] .
[10]	D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168-194, doi:10.1007/bf01584085.
[11]	M. Funk, B. Jackson, D. Labbate and J. Sheehan, 2-factor Hamiltonian graphs, J. Comb. Theory Ser. B 87 (2003), 138-144, doi:10.1016/s0095-8956(02)00031-x.
[12]	J. Hagglund and E. Steffen, Petersen-colorings and some families of snarks, Ars Math. Con-temp. 7 (2014), 161-173, doi:10.26493/1855-3974.288.11a.
[13]	A. Hakobyan and V. Mkrtchyan, S12 and P12 -colorings of cubic graphs, Ars Math. Contemp. 17 (2019), 431-445, doi:10.26493/1855-3974.1758.410.
[14]	F. Jaeger, Nowhere-zero flow problems, in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory, Volume 3, Academic Press, San Diego, CA, pp. 71-95, 1988.
[15]	L. Jin and E. Steffen, Petersen cores and the oddness of cubic graphs, J. Graph Theory 84
(2017),	109-120, doi:10.1002/jgt.22014.
[16]	T. Kaiser, D. Krâl and S. Norine, Unions of perfect matchings in cubic graphs, in: M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr (eds.), Topics in Discrete Mathematics, Springer, Berlin, volume 26 of Algorithms and Combinatorics, pp. 225-230, 2006, doi:10.1007/3-540-33700-8_14.
G. Mazzuoccolo and J. P. Zerafa: An equivalent formulation of the Fan-Raspaud Conjecture ... 
101
[17]	T. Kaiser and A. Raspaud, Perfect matchings with restricted intersection in cubic graphs, European J. Combin. 31 (2010), 1307-1315, doi:10.1016/j.ejc.2009.11.007.
[18]	D. Kräl', E. Mäcajovä, O. Pangräc, A. Raspaud, J.-S. Sereni and M. Škoviera, Projective, affine, and abelian colorings of cubic graphs, European J. Combin. 30 (2009), 53-69, doi:10.1016/j. ejc.2007.11.029.
[19]	H. Lin and X. Wang, Three matching intersection property for matching covered graphs, Discrete Math. Theor. Comput. Sci. 19 (2017), #16, doi:10.23638/dmtcs-19-3-16.
[20]	L. Loväsz and M. D. Plummer, Matching Theory, volume 121 of North-Holland Mathematics Studies, North-Holland, Amsterdam, 1st edition, 1986.
[21]	E. Mäcajovä and M. Škoviera, Fano colourings of cubic graphs and the Fulkerson conjecture, Theoret. Comput. Sci. 349 (2005), 112-120, doi:10.1016/j.tcs.2005.09.034.
[22]	E. Mäcajovä and M. Škoviera, Sparsely intersecting perfect matchings in cubic graphs, Com-binatorica 34 (2014), 61-94, doi:10.1007/s00493-014-2550-4.
[23]	G. Mazzuoccolo, Covering a cubic graph with perfect matchings, Discrete Math. 313 (2013), 2292-2296, doi:10.1016/j.disc.2013.06.006.
[24]	G. Mazzuoccolo, New conjectures on perfect matchings in cubic graphs, Electron. Notes Dis-creteMath 40 (2013), 235-238, doi:10.1016/j.endm.2013.05.042.
[25]	Z. Miao, X. Wang and C.-Q. Zhang, Unique Fulkerson coloring of Petersen minor-free cubic graphs, European J. Combin. 43 (2015), 165-171, doi:10.1016/j.ejc.2014.08.021.
[26]	V. V. Mkrtchyan, A remark on the Petersen coloring conjecture of Jaeger, Australas. J. Combin. 56 (2013), 145-151, https://ajc.maths.uq.edu.au/pdf/5 6/ajc_v56_p145. pdf.
[27]	V. V. Mkrtchyan and G. N. Vardanyan, On two consequences of Berge-Fulkerson conjecture, AKCEInt. J. Graphs Comb. (2020), doi:10.1016/j.akcej.2019.03.018.
[28]	J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891), 193-220, doi:10.1007/ bf02392606.
[29]	R. Šämal, New approach to Petersen coloring, Electron. Notes Discrete Math. 38 (2011), 755760, doi:10.1016/j.endm.2011.10.026.
[30]	E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015), 195-206, doi:10.1002/jgt.21798.
[31]	Q. Zhu, W. Tang and C.-Q. Zhang, Perfect matching covering, the Berge-Fulkerson conjecture, and the Fan-Raspaud conjecture, Discrete Appl. Math. 166 (2014), 282-286, doi:10.1016/j. dam.2013.10.008.