# Berge’s conjecture for cubic graphs
with small colouring defect

Ján Karabáš<EMAIL_ADDRESS>,  Edita Máčajová<EMAIL_ADDRESS>,
Roman Nedela<EMAIL_ADDRESS>and  Martin Škoviera<EMAIL_ADDRESS>Department of Computer Science, Faculty of Natural Sciences, Matej Bel
University, Banská Bystrica, Slovakia  Department of Computer Science,
Comenius University, Mlynská dolina, Bratislava, Slovakia  Faculty of Applied
Sciences, University of West Bohemia, Pilsen, Czech Republic  Mathematical
Institute of Slovak Academy of Sciences, Banská Bystrica, Slovakia

###### Abstract.

A long-standing conjecture of Berge suggests that every bridgeless cubic graph
can be expressed as a union of at most five perfect matchings. This conjecture
trivially holds for $3$-edge-colourable cubic graphs, but remains widely open
for graphs that are not $3$-edge-colourable. The aim of this paper is to
verify the validity of Berge’s conjecture for cubic graphs that are in a
certain sense close to $3$-edge-colourable graphs. We measure the closeness by
looking at the colouring defect, which is defined as the minimum number of
edges left uncovered by any collection of three perfect matchings. While
$3$-edge-colourable graphs have defect $0$, every bridgeless cubic graph with
no $3$-edge-colouring has defect at least $3$. In 2015, Steffen proved that
the Berge conjecture holds for cyclically $4$-edge-connected cubic graphs with
colouring defect $3$ or $4$. Our aim is to improve Steffen’s result in two
ways. First, we show that all bridgeless cubic graphs with defect $3$ satisfy
Berge’s conjecture irrespectively of their cyclic connectivity. Second, we
prove that if the graph in question is cyclically $4$-edge-connected, then
four perfect matchings suffice, unless the graph is the Petersen graph. The
result is best possible as there exists an infinite family of cubic graphs
with cyclic connectivity $3$ which have defect $3$ but cannot be covered with
four perfect matchings.

###### 2020 Mathematics Subject Classification:

05C15, 05C70; 05C75

Dedicated to professor Ján Plesnıík, our teacher and colleague.

##  1\. Introduction

In 1970’s, Claude Berge made a conjecture that every bridgeless cubic graph
$G$ can have its edges covered by at most five perfect matchings (see [23]).
The corresponding set of matchings is called a Berge cover of $G$.

Berge’s conjecture relies on the fact that every preassigned edge of $G$
belongs to a perfect matching, and hence there is a set of perfect matchings
that cover all the edges of $G$. The smallest number of perfect matchings
needed for this purpose is the perfect matching index of $G$, denoted by
$\pi(G)$. Clearly, $\pi(G)=3$ if and only if $G$ is $3$-edge-colourable, so if
$G$ has chromatic index $4$, then the value of $\pi(G)$ is believed to be
either $4$ or $5$. In this context it may be worth mentioning that
$\pi(Pg)=5$, where $Pg$ denotes the Petersen graph, and that cubic graphs with
$\pi=5$ are very rare [3, 21].

Berge’s conjecture is closely related to a stronger and arguably more famous
conjecture of Fulkerson [9], attributed also to Berge and therefore often
referred to as the Berge-Fulkerson conjecture [26]. The latter conjecture
suggests that every bridgeless cubic graph contains a collection of six
perfect matchings such that each edge belongs to precisely two of them.
Fulkerson’s conjecture clearly implies Berge’s. Somewhat surprisingly, the
converse holds as well, which follows from an ingenious construction due to
Mazzuoccolo [23].

Very little is known about the validity of either of these conjectures.
Besides the $3$-edge-colourable cubic graphs, the conjectures are known to
hold only for a few classes of graphs, mostly possessing a very specific
structure (see [5, 8, 10, 11, 17, 22]). On the other hand, it has been proved
that if Fulkerson’s conjecture is false, then the smallest counterexample
would be cyclically $5$-edge-connected (Máčajová and Mazzuoccolo [20]).

In this paper we investigate Berge’s conjecture under more general
assumptions, not relying on any specific structure of graphs: our aim is to
verify the conjecture for all cubic graphs that are, in a certain sense, close
to $3$-edge-colourable graphs. In our case, the proximity to $3$-edge-
colourable graphs will be measured by the value of their colouring defect. The
colouring defect of a cubic graph, or just defect for short, is the smallest
number of edges that are left uncovered by any set of three perfect matchings.
This concept was introduced and thoroughly studied by Steffen [28] in 2015 who
used the notation $\mu_{3}(G)$ but did not coin any term for it. Since a cubic
graph has defect $0$ if and only if it is $3$-edge-colourable, colouring
defect can serve as one of measures of uncolourability of cubic graphs, along
with resistance, oddness, and other similar invariants recently studied by a
number of authors, see for example [1, 2, 7].

In [28, Corollary 2.5] Steffen proved that the defect of every bridgeless
cubic graph that cannot be $3$-edge-coloured is at least $3$, and can be
arbitrarily large. He also proved that every cyclically $4$-edge-connected
cubic graph with defect $3$ or $4$ satisfies Berge’s conjecture [28, Theorem
2.14].

We strengthen the latter result in two ways.

First, we show that every bridgeless cubic graph with defect $3$ satisfies the
Berge conjecture irrespectively of its cyclic connectivity.

######  Theorem 1.1.

Every bridgeless cubic graph with colouring defect $3$ admits a Berge cover.

Second, we prove that if the graph in question is cyclically $4$-edge-
connected, then four perfect matchings are enough to cover all its edges,
except for the Petersen graph. The existence of a cover with four perfect
matchings is known to have a number of important consequences. For example,
such a graph satisfies the Fan-Raspaud conjecture [6], admits a $5$-cycle
double cover and has a cycle cover of length $4/3\cdot m$, where $m$ is the
number of edges [28, Theorem 3.1].

######  Theorem 1.2.

Let $G$ be a cyclically $4$-edge-connected cubic graph with defect $3$. Then
$\pi(G)=4$, unless $G$ is the Petersen graph.

Theorem 1.2 is best possible in the sense that there exist infinitely many
$3$-connected cubic graphs with colouring defect $3$ that cannot be covered
with four perfect matchings.

Our proofs use a wide range of methods. Both main results rely on Theorem 4.1
which describes the structure of a subgraph resulting from the removal of a
$6$-edge-cut from a bridgeless cubic graph. Moreover, the proof of Theorem 1.2
establishes an interesting relationship between the colouring defect and the
bipartite index of a cubic graph. We recall that the bipartite index of a
graph is the smallest number of edges whose removal yields a bipartite graph.
This concept was introduced by Thomassen in [30] and was applied in [30, 31]
in a different context.

In closing, we would like to mention that our Theorem 1.1 can be alternatively
derived from a recent result published in [29], which states that every
bridgeless cubic graph containing two perfect matchings that share at most one
edge admits a Berge cover. The two results are connected via an inequality
between two uncolourability measures proved in [13, Theorem 2.2] (see also
[15, Proposition 4.2]). Although the main result of [29] is important and
interesting, its proof is very technical and difficult to comprehend, which is
why we have not been able to verify all its details. We believe that more
effort is needed to clarify the arguments presented in [29].

Our paper is organised as follows. The next section summarises definitions and
results needed for understanding the rest of the paper. Section 3 provides a
brief account of the theory surrounding the notion of colouring defect.
Specific tools needed for the proofs of Theorems 1.1 and 1.2 are established
in Section 4. The two theorems are proved in Sections 5 and 6, respectively.
The final section illustrates that the condition on cyclic connectivity in
Theorem 1.2 cannot be removed.

##  2\. Preliminaries

2.1. Graphs. Graphs studied in this paper are finite and mostly cubic (that
is, 3-valent). Multiple edges and loops are permitted. The _order_ of a graph
$G$, denoted by $|G|$, is the number of its vertices. A _circuit_ in $G$ is a
connected $2$-regular subgraph of $G$. A $k$-_cycle_ is a circuit of length
$k$. The _girth_ of $G$ is the length of a shortest circuit in $G$.

An _edge cut_ is a set $R$ of edges of a graph whose deletion yields a
disconnected graph. A common type of an edge cut arises by taking a subset of
vertices or an induced subgraph $H$ of $G$ and letting $R$ to be the set
$\delta_{G}(H)$ of all edges with exactly one end in $H$. We omit the
subscript $G$ whenever $G$ is clear from the context.

A connected graph $G$ is said to be _cyclically $k$-edge-connected_ for some
integer $k\geq 1$ if the removal of fewer than $k$ edges cannot leave a
subgraph with at least two components containing circuits. The _cyclic
connectivity_ of $G$ is the largest integer $k$ not exceeding the cycle rank
(Betti number) of $G$ such that $G$ is cyclically $k$-edge-connected. An edge
cut $R$ in $G$ that separates two circuits from each other is _cycle-
separating_. It is not difficult to see that the set $\delta_{G}(C)$ leaving a
shortest circuit $C$ of a cubic graph $G$ is cycle-separating unless $G$ is
the complete bipartite graph $K_{3,3}$, the complete graph $K_{4}$, or the
_$3$ -dipole_, the graph which consists of two vertices and three parallel
edges joining them. Observe that an edge cut formed by a set of independent
edges is always cycle-separating. Conversely, a cycle-separating edge cut of
minimum size is independent.

2.2. Edge colourings and flows. An _edge colouring_ of a graph $G$ is a
mapping from the edge set of $G$ to a set of colours. A colouring is _proper_
if any two edge-ends incident with the same vertex receive distinct colours. A
_$k$ -edge-colouring_ is a proper edge colouring where the set of colours has
$k$ elements. Unless specified otherwise, our colouring will be assumed to be
proper and graphs to be _subcubic_ , that is, with vertices of valency $1$,
$2$, or $3$.

There is a standard method of transforming a $3$-edge-colouring to another
$3$-edge-colouring: it uses so-called Kempe switches: Let $G$ be a subcubic
graph endowed with a proper $3$-edge-colouring $\sigma$. Take two distinct
colours $i$ and $j$ from $\\{1,2,3\\}$. An _$(i,j)$ -Kempe chain_ in $G$ (with
respect to $\sigma$) is a non-extendable walk $L$ that alternates edges
coloured $i$ with those coloured $j$. It is easy to see that $L$ is either a
bicoloured circuit or path starting and ending at the vertex of valency
smaller than $3$. The _Kempe switch_ along a Kempe chain produces a new
$3$-edge-colouring of $G$ by interchanging the colours on $L$.

It is often useful to regard $3$-edge-colourings of cubic graphs as nowhere-
zero flows. To be more precise, one can identify each colour from the set
$\\{1,2,3\\}$ with its binary representation; thus $1=(0,1)$, $2=(1,0)$, and
$3=(1,1)$. Having done this, the condition that the three colours meeting at
every vertex $v$ are all distinct becomes equivalent to requiring the sum of
the colours at $v$ to be $0=(0,0)$. The latter is nothing but the Kirchhoff
law for nowhere-zero $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$-flows. Recall that
an $A$-flow on a graph $G$ is a pair $(D,\phi)$ where $\phi$ is an assignment
of elements of an abelian group $A$ to the edges of $G$, and $D$ is an
assignment of one of two directions to each edge in such a way that, for every
vertex $v$ in $G$, the sum of values flowing into $v$ equals the sum of values
flowing out of $v$ (_Kirchhoff’s law_). A _nowhere-zero_ $A$-flow is one which
does not assign $0\in A$ to any edge of $G$. If each element $x\in A$
satisfies $x=-x$, then $D$ can be omitted from the definition. It is well
known that the latter is satisfied if and only if $A\cong\mathbb{Z}_{2}^{n}$
for some $n\geq 1$.

The following well-known statement is a direct consequence of Kirchhoff’s law.

######  Lemma 2.1.

(Parity Lemma) Let $G$ be a cubic graph endowed with a $3$-edge-colouring
$\xi$. The following holds for every edge cut $\delta_{G}(H)$, where $H$ is a
subgraph of $G$:

$\sum_{e\in\delta_{G}(H)}\xi(e)=0.$

Equivalently, the number of edges in $\delta_{G}(H)$ carrying any fixed colour
has the same parity as the size of the cut.

A cubic graph $G$ is said to be _colourable_ if it admits a $3$-edge-
colouring. A $2$-connected cubic graph that admits no $3$-edge-colouring is
called a _snark_. Our definition agrees with that of Cameron et al. [4],
Nedela and Škoviera [24], Steffen [27], and others, and leaves the concept of
a snark as wide as possible. A more restrictive definition requires a snark to
be to be cyclically $4$-edge-connected, with girth at least $5$, see for
example [7]. We call such snarks _nontrivial_.

2.3. Perfect matchings. The classical theorems of Tutte [32] and Plesník [25],
stated below, will be repeatedly used throughout the paper, albeit in a
slightly modified form permitting parallel edges and loops. These extensions
can be proved easily by using the standard versions of the corresponding
theorems.

Let $\operatorname{odd}(G)$ denote the number of _odd components_ of $G$, that
is, the components with an odd number of vertices.

######  Theorem 2.2.

(Tutte, 1947) A graph $G$, possibly containing parallel edges and loops, has a
perfect matching if and only if

$\operatorname{odd}(G-S)\leq|S|\quad\text{for all }S\subseteq V(G).$

######  Theorem 2.3.

(Plesník, 1972) Let $G$ be an $(r-1)$-edge-connected $r$-regular graph with
$r\geq 1$, and let $A$ be an arbitrary set of $r-1$ edges in $G$. If $G$ has
even order, then $G-A$ has a perfect matching.

##  3\. Colouring defect of a cubic graph

In this section we discuss a number of structures related to the concept of
colouring defect, which will be used in the proofs of Theorems 1.1 and 1.2.
More details on this matter can be found in [16] and [28].

For a bridgeless cubic graph $G$ we define a _$k$ -array of perfect
matchings_, or briefly a _$k$ -array_ of $G$, as an arbitrary collection
$\mathcal{M}=\\{M_{1},M_{2},\ldots,M_{k}\\}$ of $k$ perfect matchings of $G$,
not necessarily pairwise distinct. The concept of a $k$-array unifies a number
of notions, such as Berge covers, Fulkerson covers, Fan-Raspaud triples, and
others. Our main concern here are $3$-arrays, which we regard as
approximations of $3$-edge-colourings.

Let $\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ be a $3$-array of perfect matchings
of a cubic graph $G$. An edge of $G$ that belongs to at least one of the
perfect matchings of $\mathcal{M}$ will be considered to be _covered_. An edge
will be called _uncovered_ , _simply covered_ , _doubly covered_ , or _triply
covered_ if it belongs, respectively, to zero, one, two, or three distinct
members of $\mathcal{M}$.

Given a cubic graph $G$, it is natural task to maximise the number of covered
edges, or equivalently, to minimise the number of uncovered ones. A $3$-array
that leaves the minimum number of uncovered edges will be called _optimal_.
The number of edges left uncovered by an optimal $3$-array is the _colouring
defect_ of $G$, or the _defect_ for short, denoted by $\mathrm{df}({G})$.

Let $\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ be a $3$-array of perfect matchings
of a cubic graph $G$. One way to describe $\mathcal{M}$ is based on regarding
the indices $1$, $2$, and $3$ as colours. Since the same edge may belong to
more than one member of $\mathcal{M}$, an edge of $G$ may receive more than
one colour. To each edge $e$ of $G$ we can therefore assign the list $\phi(e)$
of all colours in lexicographic order it receives from $\mathcal{M}$. We let
$w(e)$ denote the number of colours in the list $\phi(e)$ and call it the
_weight_ of $e$ (with respect to $\mathcal{M}$). In this way $\mathcal{M}$
gives rise to a colouring

$\phi\colon E(G)\to\\{\emptyset,1,2,3,12,13,23,123\\}$

where $\emptyset$ denotes the empty list. Obviously, a mapping $\sigma$
assigning subsets of $\\{1,2,3\\}$ to the edges of $G$ determines a $3$-array
if and only if, for each vertex $v$ of $G$, each element of $\\{1,2,3\\}$
occurs precisely once in the subsets of $\\{1,2,3\\}$ assigned by $\sigma$ to
the edges incident with $v$. In general, $\phi$ need not be a proper edge-
colouring. However, since $M_{1}$, $M_{2}$, and $M_{3}$ are perfect matchings,
the only possibility when two edges equally coloured under $\phi$ meet at a
vertex is that both of them receive colour $\emptyset$. In this case the third
edge incident with the vertex is coloured $123$.

A different but equivalent way of representing a $3$-array uses a mapping

$\chi\colon E(G)\to\mathbb{Z}_{2}^{3},\quad
e\mapsto\chi(e)=(x_{1},x_{2},x_{3})$

defined by setting $x_{i}=0$ if and only if $e\in M_{i}$, where
$i\in\\{1,2,3\\}$. Since the complement of each $M_{i}$ in $G$ is a
$2$-factor, it is easy to see that $\chi$ is a $\mathbb{Z}_{2}^{3}$-flow. We
call $\chi$ _the characteristic flow_ for $\mathcal{M}$. Again, $\chi$ is a
nowhere-zero $\mathbb{Z}_{2}^{3}$-flow if and only if $G$ contains no triply
covered edge. In the context of $3$-arrays the characteristic flow was
introduced in [14, p. 166]. Observe that the characteristic flow $\chi$ of a
$3$-array and the colouring $\phi$ determine each other. In particular, the
condition on $\phi$ requiring all three indices from $\\{1,2,3\\}$ to occur
precisely once in a colour around any vertex is equivalent to Kirchhoff’s law.

The following result characterises $3$-arrays with no triply covered edge.

######  Proposition 3.1.

Let $\mathcal{M}$ be a $3$-array of perfect matchings of a cubic graph $G$.
The following three statements are equivalent.

  1. (i)

$G$ has no triply covered edge with respect to $\mathcal{M}$.

  2. (ii)

The associated colouring $\phi\colon
E(G)\to\\{\emptyset,1,2,3,12,13,23,123\\}$ is proper.

  3. (iii)

The characteristic flow $\chi$ for $\mathcal{M}$, with values in
$\mathbb{Z}_{2}^{3}$, is nowhere-zero.

The next important structure associated with a $3$-array is its core. The
_core_ of a $3$-array $\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ of $G$ is the
subgraph of $G$ induced by all the edges of $G$ that are not simply covered;
we denote it by ${\mathrm{core}}(\mathcal{M})$. The core is called _optimal_
whenever $\mathcal{M}$ is optimal.

It is worth mentioning that if $G$ is $3$-edge-colourable and $\mathcal{M}$
consists of three pairwise disjoint perfect matchings, then
${\mathrm{core}}(\mathcal{M})$ is empty. If $G$ is not $3$-edge-colourable,
then every core must be nonempty. Figure 1 shows the Petersen graph endowed
with a $3$-array whose core is its “outer” $6$-cycle. The hexagon is in fact
an optimal core.

Figure 1. An optimal $3$-array of the Petersen graph

The following proposition, due to Steffen [28, Lemma 2.2], describes the
structure of optimal cores in the general case.

######  Proposition 3.2.

Let $\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ be an optimal $3$-array of perfect
matchings of a snark $G$. Then every component of
${\mathrm{core}}(\mathcal{M})$ is either an even circuit of length at least
$6$ or a subdivision of a cubic graph. Moreover, the union of doubly and
triply covered edges forms a perfect matching of
${\mathrm{core}}(\mathcal{M})$.

The next theorem characterises snarks with minimal possible colouring defect.
The lower bound for the defect of a snark – the value $3$ – is due to Steffen
[28, Corollary 2.5].

######  Theorem 3.3.

Every snark $G$ has $\mathrm{df}({G})\geq 3$. Furthermore, the following three
statements are equivalent.

  1. (i)

$\mathrm{df}({G})=3$.

  2. (ii)

The core of any optimal $3$-array of $G$ is a $6$-cycle.

  3. (iii)

$G$ contains an induced $6$-cycle $C$ such that the subgraph $G-E(C)$ admits a
proper $3$-edge-colouring under which the six edges of $\delta(C)$ receive
colours $1,1,2,2,3,3$ with respect to the cyclic order induced by an
orientation of $C$.

Figure 2. The hexagonal core and its vicinity.

If $G$ is an arbitrary snark with $\mathrm{df}({G})=3$, then, by Theorem 3.3
(iii), $G$ contains an induced $6$-cycle $C=(e_{0}e_{1}e_{2}e_{3}e_{4}e_{5})$
such that $G-E(C)$ is $3$-edge-colourable. We say that that $C$ is a
_hexagonal core_ of $G$.

Let $f_{i}$ denote the edge of $\delta(C)$ which is incident with $e_{i-1}$
and $e_{i}$, where $i\in\\{0,1,\ldots,5\\}$ and the indices are reduced modulo
$6$; see Figure 2. Since $G-E(C)$ is $3$-edge-colourable but $G$ is not, it is
not difficult to see that for every $3$-edge-colouring of $G-E(C)$ the cyclic
order of colours around $C$ is $(1,1,2,2,3,3)$ up to permutation of colours.
Moreover, we can assume that the values of the associated colouring $\phi$ of
$G$ induced by $\mathcal{M}$ in the vicinity of $C$ are those as shown in
Figure 2, or can be obtained from them by the rotation one step clockwise.
Note that the two possibilities only depend on the position of the uncovered
edges. In any case, there are no triply covered edges, and so $\phi$ is a
proper edge colouring due to Proposition 3.2.

We finish this section by stating the following property of a hexagonal core,
which will be needed in Sections 6. We leave the proof to the reader or refer
to [16].

######  Lemma 3.4.

Let $G$ be a snark with $\mathrm{df}({G})=3$. If a hexagonal core of $G$
intersects a triangle or a quadrilateral, then the intersection consists of a
single uncovered edge.

##  4\. Tools

In this section we establish tools for proving Theorems 1.1 and 1.2. Its main
results are stated as Theorems 4.1 and 4.4, both having somewhat bipartite
flavour. The first theorem suggests that if a subgraph $H$ of a bridgeless
cubic graph is separated from the rest by a $6$-edge-cut and has no perfect
matching, then the structure of $H$ is – essentially – that of a bipartite
cubic graph. Moreover, only one of the two parts is incident with the cut.

######  Theorem 4.1.

Let $G$ be a bridgeless cubic graph and let $H\subseteq G$ be a subgraph with
$|\delta_{G}(H)|=6$. Then $H$ has a perfect matching, or else $H$ contains an
independent set $S$ of trivalent vertices such that

  * (i)

every component of $H-S$ is odd,

  * (ii)

$\operatorname{odd}(H-S)=|S|+2$, and

  * (iii)

$|\delta_{G}(L)|=3$ for each component $L$ of $H-S$.

###### Proof.

Set $K=G-V(H)$. Assume that $H$ has no perfect matching. Tutte’s Theorem tells
us that there exists a set $S\subseteq V(H)$ such that
$\operatorname{odd}(H-S)>|S|$. As $H$ has an even number of vertices, the
numbers $|S|$ and $\operatorname{odd}(H-S)$ have the same parity, so

$\operatorname{odd}(H-S)-|S|\geq 2.$ (1)

Set $a=|\delta_{G}(S)\cap\delta_{G}(K)|$. Clearly, $a\in\\{0,1,\ldots,6\\}$.
Since $|\delta_{H}(S)|+a=|\delta_{G}(S)|\leq 3|S|$, we get

$|\delta_{H}(S)|\leq 3|S|-a.$ (2)

To bound $|\delta_{H}(S)|$ from below, we first realise that each odd
component of $H-S$ is incident with at least three edges of $\delta_{G}(H-S)$
because $G$ is bridgeless. Moreover, there are $6-a$ edges joining $H-S$ to
$K$ (see Figure 3). Therefore

$|\delta_{H}(S)|=|\delta_{H}(H-S)|=|\delta_{G}(H-S)|-(6-a)\geq
3\cdot\operatorname{odd}(H-S)-(6-a).$ (3)

If we combine (2) with (3), we get

$3\cdot\operatorname{odd}(H-S)-6+a\leq|\delta_{H}(S)|\leq 3|S|-a.$ (4)

Since $3\cdot\operatorname{odd}(H-S)-3|S|\geq 6$ according to (1), we can
rewrite (4) as

$-2a\geq 3\cdot\operatorname{odd}(H-S)-3|S|-6\geq 0,$

which implies that $a=0$.

Now we insert $a=0$ into (4) and get $3\cdot\operatorname{odd}(H-S)-3|S|\leq
6$. Together with (1), multiplied by $3$, this yields that

$3\cdot\operatorname{odd}(H-S)-6\leq|\delta_{H}(S)|\leq 3|S|\leq
3\cdot\operatorname{odd}(H-S)-6.$

Figure 3. The structure of $G$ as described in the proof of Theorem 4.1.

Hence,

$|\delta_{H}(S)|=3|S|=3\cdot\operatorname{odd}(H-S)-6,$ (5)

which implies that $S$ is an independent set of $H$, with all its vertices
$3$-valent, and that each component $K$ of $H-S$ is odd with
$|\delta_{G}(K)|=3$. Thus we have proved Statements (i) and (iii). Moreover,
Equation (5) implies statement (ii). The proof is complete. ∎

######  Example 4.2.

We illustrate Theorem 4.1 in two simple instances. First, if $G$ is the
$3$-dimensional cube $Q_{3}$ and $H=G-V(C)$, where $C$ is an induced $6$-cycle
of $G$, then Theorem 4.1 holds with $S=\emptyset$. If $G$ is the Petersen
graph $Pg$ and $H=G-V(C)$, where $C$ is again a $6$-cycle, then $H$ is
isomorphic to the complete bipartite graph $K_{1,3}$ and $S$ is constituted by
its central vertex.

We proceed to our second tool, which describes cubic graphs just one step away
from being bipartite. Recall that if a cubic graph is bipartite, then it is
obviously bridgeless. Moreover, if it is connected, then its bipartition is
uniquely determined. On the other hand, if a cubic graph is not bipartite,
then, clearly, at least two edges have to be removed in order to produce a
bipartite graph. Motivated by these two facts we define a cubic graph $G$ to
be _almost bipartite_ if it is bridgeless, not bipartite, and contains two
edges $e$ and $f$ such that $G-\\{e,f\\}$ is a bipartite graph. The edges $e$
and $f$ are said to be _surplus edges_ of $G$. If a cubic graph is almost
bipartite, then there exists a component $K$ of $G$ such that the surplus
edges connect vertices within different partite sets of $K$.

Our aim is to show that every almost bipartite graph is $3$-edge-colourable.
We start with the following.

######  Proposition 4.3.

Every almost bipartite cubic graph has a perfect matching that contains both
surplus edges.

###### Proof.

Let $G$ be an almost bipartite cubic graph with surplus edges $e$ and $f$.
Since $e$ and $f$ belong to the same component of $G$, we may assume that $G$
is connected. Let $\\{A,B\\}$ be the bipartition of $G^{\prime}=G-\\{e,f\\}$.
As said before, the endvertices of one of the surplus edges, say $e$, belong
to $A$ and those of $f$ then belong to $B$. In particular, this means that
$|A|=|B|=n$ for some positive integer $n$. By Theorem 2.3, there exists a
perfect matching $M$ containing the edge $e$. There are $n-2$ edges of $M$
that match $n-2$ vertices of $A$ to $n-2$ vertices of $B$. It follows that
$f\in M$. ∎

We would like to mention that our Proposition 4.3 has been inspired by Lemma 3
(iii) of [19]. In principle, the mentioned lemma could be used to prove
Proposition 4.3, however, the proof would not be anything close to being
straightforward.

We are now ready for the following theorem.

######  Theorem 4.4.

Every almost bipartite cubic graph is $3$-edge-colourable.

###### Proof.

Let $G$ be an almost bipartite graph with surplus edges $e$ and $f$. By
Proposition 4.3, $G$ has a perfect matching $M$ which includes both $e$ and
$f$. Now, $G-M$ is bipartite $2$-regular spanning subgraph of $G$, so each
component of $G-M$ is an even circuit. It means that $G-M$ can be decomposed
into two disjoint perfect matchings $N_{1}$ and $N_{2}$. Put together, $M$,
$N_{1}$, and $N_{2}$ are colour classes of a proper $3$-edge-colouring of $G$.
∎

The previous theorem links the problem of $3$-edge-colourability of cubic
graphs to an important concept of a bipartite index, which has been introduced
to measure how far a graph is from being bipartite. Following [31, Definition
2.4], we define the _bipartite index_ $\operatorname{bi}(G)$ of a graph $G$ to
be the smallest number of edges that must be deleted in order to make the
graph bipartite. In other words, the bipartite index of a graph is the number
of edges outside a maximum edge cut.

Our Theorem 4.4 states that all bridgeless cubic graphs with bipartite index
at most two are $3$-edge colourable. This is, in fact, best possible as there
exist infinitely many nontrivial snarks whose bipartite index equals $3$: this
is true, for example, for the Petersen graph or for all Isaacs flower snarks
$J_{2n+1}$; see [12] for the definition and Figure 4 for $J_{7}$.

Figure 4. The flower snark $J_{7}$

Threorem 4.4 thus suggests that, along with oddness, resistance, flow
resistance, and other similar invariants extensively studied in [7], bipartite
index can serve as another measure of uncolourability of cubic graphs. It is
easy to see, for example, that for a cubic graph
$\operatorname{bi}(G)\geq\omega(G)$, where $\omega(G)$ denotes the _oddness_
of a cubic graph, that is, the smallest number of odd circuits in a $2$-factor
of $G$. Since there exist snarks of arbitrarily large oddness [18], there are
snarks of arbitrarily large bipartite index.

##  5\. Proof of Theorem 1.1

The purpose of this section is to establish the existence of a Berge cover for
every bridgeless cubic graph of defect $3$ (Theorem 1.1) and for every
cyclically $4$-edge-connected cubic graph of defect $4$. We begin with the
following auxiliary result.

######  Lemma 5.1.

Let $G$ be a cubic graph of defect $3$ and let
$\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ be an optimal $3$-array of perfect
matchings for $G$. Then $G$ has a fourth perfect matching $M_{4}$ which covers
at least two of the three edges left uncovered by $\mathcal{M}$.

###### Proof.

Consider the $6$-cycle $C=(e_{0}e_{1}\ldots e_{5})$ constituting the core of
$\mathcal{M}$. We adopt the notation introduced in Figure 2; in particular,
$e_{1}$, $e_{3}$, and $e_{5}$ are the three uncovered edges of $C$. We also
assume that the edge colouring $\phi$ associated with $\mathcal{M}$ takes
values as indicated in Figure 2. By Proposition 3.1, the colouring is proper.

An uncovered edge $e_{i}$ of $C$ will be considered _bad_ if $G$ has a cycle-
separating $3$-edge-cut $R_{i}$ containing the edges $e_{i-1}$ and $e_{i+1}$.
We claim that not all of the edges $e_{1}$, $e_{3}$, and $e_{5}$ can be bad.
Suppose to the contrary that all of them are bad. For $i\in\\{1,3,5\\}$ let
$h_{i}$ denote the third edge of the cut $R_{i}$. Since the edges $f_{i}$ and
$f_{i+1}$ of $\delta_{G}(C)$ are both adjacent to $e_{i}$, the set
$R_{i}^{\prime}=\\{f_{i},f_{i+1},h_{i}\\}$ is also a $3$-edge-cut. Moreover,
all three edges of $R_{i}^{\prime}$ are simply covered. Let $L_{i}$ be the
component of $G-R_{i}^{\prime}$ that does not contains $e_{i}$.

Figure 5. Constructing a $3$-edge-colouring of $G$ provided that $G$ has three
bad edges. The stage preceding Kempe switches.

Recall that the restriction of $\phi$ to $G-E(C)$ is a proper $3$-edge-
colouring. We show that this colouring can be modified and extended to a
$3$-edge-colouring $\psi$ of the entire $G$. By Kirchhoff’s law,
$\phi(f_{1})+\phi(f_{2})+\phi(h_{1})=0$. Since $\phi(f_{1})=3$, and
$\phi(f_{2})=2$, we have $\phi(h_{1})=1$. Similarly, $\phi(h_{3})=3$ and
$\phi(h_{5})=2$. To define $\psi$, we first set $\psi(e_{1})=1$,
$\psi(e_{3})=3$, and $\psi(e_{5})=2$, and extend this definition to the
uncovered edges of $G$ in such a way that the hexagon $C$ is properly
coloured. The values of $\psi$ on $C$ now cause a conflict with the values of
$\phi$ on $\delta_{G}(C)$ at each vertex of $C$. However, this problem can
easily be resolved by the use of suitable Kempe switches. Indeed, take the
$(3,2)$-Kempe chain in $G-E(C)$ with respect to $\phi$ that starts with the
edge $f_{1}$ coloured $3$; denote the Kempe chain by $B_{1}$. Clearly, $B_{1}$
leaves $L_{1}$ through either $h_{1}$ or $f_{2}$. However, $\phi(h_{1})=1$, so
$B_{1}$ ends with $f_{2}$ (see Figure 5). After switching the colours of
$\phi$ on $B_{1}$ we produce a new $3$-edge-colouring of $G-E(C)$, in which
the colouring conflicts at the vertices $v_{1}$ and $v_{2}$ have been removed.
Proceeding similarly with Kempe chains stating at $f_{3}$ and $f_{5}$ we
resolve the conflicts at the remaining vertices of $C$ and eventually obtain
the required proper $3$-edge-colouring $\psi$ of $G$. Since $G$ is a snark,
this cannot occur. Therefore, at least one uncovered edge of $C$ must not be
bad.

Without loss of generality we may assume that the edge $e_{1}$ is not bad.
Take the path $P=e_{3}e_{4}e_{5}\subseteq C$ and set $H=G-V(P)$. Clearly,
$|\delta_{G}(H)|=6$, so Theorem 4.1 applies. We claim that $H$ admits a
perfect matching. Suppose not. Then, by Theorem 4.1, $H$ contains an
independent set $S$ of vertices such that each component $L$ of $H-S$ has
$|\delta_{G}(L)|=3$ and each edge of $\delta_{G}(H)$ joins a vertex of $H-S$
to a vertex of $P$. Since the edge $e_{1}$ belongs to $H-S$, the component
containing $e_{1}$ is nontrivial. It follows that $e_{1}$ is bad, and we have
arrived at a contradiction. Thus $H$ admits a perfect matching, and this
matching is readily extended to a perfect matching $M_{4}$ of $G$ that covers
the uncovered edges $e_{3}$ and $e_{5}$. The proof is complete. ∎

###### Proof of Theorem 1.1.

Take an optimal $3$-array $\\{M_{1},M_{2},M_{3}\\}$ for $G$. It leaves three
uncovered edges. According to Lemma 5.1, there is a perfect matching $M_{4}$
that covers at least two of them. The remaining uncovered edge (if any) can be
covered by a perfect matching $M_{5}$ guaranteed by Theorem 2.3. Together
these perfect matchings a Berge cover of $G$. ∎

In the rest of this section we prove that every cyclically $4$-edge-connected
cubic graph with defect $4$ admits a Berge cover. Our proof significantly
differs from the one provided by Steffen [28, Theorem 2.14] in that it avoids
the use of Seymour’s results on $p$-tuple multicolourings [26] by employing
Theorem 4.1 instead.

First we establish the following lemma.

######  Lemma 5.2.

Let $G$ be a cyclically $4$-edge-connected cubic graph. If $G$ has an optimal
$3$-array whose core is a circuit of length $d$, then $\pi(G)\leq 3+\lceil
d/4\rceil$.

###### Proof.

Let $\mathcal{M}$ be an optimal $3$-array of $G$ whose core is a circuit $C$
of length $d$. By Proposition 3.2, $C$ alternates uncovered and doubly covered
edges; in particular, $d$ is even. Note that $d\geq 6$ by Proposition 3.2.

Let $P=efg\subseteq C$ be an arbitrary path of length $3$ whose middle edge is
doubly covered. We show that $G$ has a perfect matching containing both
uncovered edges of $P$. Set $H=G-V(P)$. If $H$ has a perfect matching, say
$M$, then $M\cup\\{e,g\\}$ is a perfect matching of $G$ containing both $e$
and $g$, and we are done. Thus we may assume that $H$ has no perfect matching.
By Theorem 4.1, there exists an independent set $S\subseteq V(H)$ such that
$H-S$ satisfies Items (i)–(iii) of the theorem. In particular, each component
$L$ of $H-S$ is odd and has $|\delta_{G}(L)|=3$. Since $G$ has no non-trivial
$3$-cuts, each component is just a vertex, implying that $H$ is a bipartite
graph. It follows that $C\cap H$ is a path of even length, and hence
$|E(C)|=|E(C\cap H)|+5$ is an odd number, which is impossible. We have thus
proved that there exists a perfect matching containing any two uncovered edges
of $C$ joined by a doubly covered edge.

Now we finish the proof. It is easy to see that $C$ contains $\lfloor
d/4\rfloor$ pairwise edge-disjoint paths of length 3 that begin and end with
an uncovered edge. At most one uncovered edge remains outside these paths,
which means that the uncovered edges of $C$ can be covered by at most $\lceil
d/4\rceil$ paths of length 3 that begin and end with an uncovered edge. In
other words, there exists a set $\mathcal{S}$ of $\lceil d/4\rceil$ perfect
matchings that collectively contain all uncovered edges. Hence,
$\pi(G)\leq|\mathcal{M}\cup\mathcal{S}|\leq 3+\lceil d/4\rceil$, as claimed. ∎

######  Theorem 5.3.

Every cyclically $4$-edge-connected cubic graph of defect $4$ admits a Berge
cover.

###### Proof.

Let $G$ be a cyclically $4$-edge-connected cubic graph of defect $4$.
Proposition 3.2 implies that any core with four uncovered edges must be either
an 8-cycle or a subgraph consisting of two disjoint triangles joined by a
triply covered edge. Since $G$ is cyclically $4$-edge-connected, the latter
possibility does not occur. Hence, the core of any optimal $3$-array for $G$
is an 8-cycle, and the result follows from Lemma 5.2. ∎

##  6\. Proof of Theorem 1.2

We prove that every cyclically $4$-edge-connected cubic graph $G$ of defect
$3$ has $\pi(G)=4$ with the only exception of the Petersen graph.

###### Proof of Theorem 1.2.

Let $G$ be a cyclically $4$-edge-connected cubic graph with
$\mathrm{df}({G})=3$ and $\pi(G)>4$. Our aim is to show that $G$ is isomorphic
to the Petersen graph.

Let $C=(e_{0}e_{1}\ldots e_{5})$ be the hexagonal core of an optimal $3$-array
$\mathcal{M}=\\{M_{1},M_{2},M_{3}\\}$ of $G$, and let $H=G-V(C)$. We may
assume that the colouring $\phi$ associated with $\mathcal{M}$ and the names
of the vertices and edges in the vicinity of $C$ are as in Figure 2. In
particular, the endvertices of the edges of the cut $\delta_{G}(C)$ not lying
on $C$ are $u_{0}$, $u_{1}$, …, $u_{5}$ and are listed in a cyclic order
around $C$. Set $U=\\{u_{0},\ldots,u_{5}\\}$.

Claim 1. _The subgraph $H$ is bipartite._

_Proof of Claim 1._ If $H$ contains a perfect matching, then the matching can
be extended to a perfect matching $M_{4}$ of $G$ which covers the three
uncovered edges of $C$. It follows that $\pi(G)=4$, contrary to our
assumption. Therefore $H$ has no perfect matching. In this situation Theorem
4.1 tells us that there exists a set $S\subseteq V(H)$ such that each
component $L$ of $H-S$ has $|\delta_{G}(L)|=3$ and each edge of
$\delta_{G}(H)$ joins a vertex of $H-S$ to a vertex of $C$. As $G$ is
cyclically 4-edge-connected, each component of $H-S$ is a single vertex.
Consequently, $H$ is a bipartite graph with bipartition $\\{S,V(H)-S\\}$ and
edge set $\delta_{G}(S)$. This establishes Claim 1.

Next we explore the colouring properties of the subgraph
$H^{+}=G-E(C)\subseteq G$. Note that $H^{+}=H+\\{f_{0},f_{1},\ldots,f_{5}\\}$
and $H^{+}\cup C=G$. Set $C^{+}=C+\\{f_{0},f_{1},\ldots,f_{5}\\}$. In $C^{+}$,
the endvertices $u_{0}$, $u_{1}$, …, $u_{5}$ are assumed as pairwise distinct.

Before proceeding further we need several definitions. A _colour vector_ is
any sequence $\alpha=c_{0}c_{1}\ldots c_{5}$ of six colours
$c_{i}\in\\{1,2,3\\}$ satisfying Parity Lemma; that is,
$c_{0}+\ldots+c_{5}=0$. Every $3$-edge-colouring $\sigma$ of $H^{+}$ thus
_induces_ the colour vector
$\alpha_{\sigma}=\sigma(f_{0})\sigma(f_{1})\ldots\sigma(f_{5})$. By permuting
the colours $1$, $2$, and $3$ in $\alpha$ we obtain a new colour vector,
nevertheless, the difference between the two is insubstantial. Therefore each
of the six permutations of colours produces a sequence that encodes
essentially ‘the same colour vector’. In order to have a canonical
representative, we choose from them the lexicographically minimal sequence and
call it the _type_ of $\alpha$. A _colouring type_ is the type of some colour
vector $\alpha$. The _type_ of a $3$-edge-colouring $\sigma$ of $H^{+}$ is the
type of the induced colour vector
$\sigma(f_{0})\sigma(f_{1})\ldots\sigma(f_{5})$. A colouring type is said to
be _admissible_ for $H^{+}$ if it is the type of a certain $3$-edge-colouring
of $H^{+}$. Similar definitions apply to $C^{+}$.

Claim 2. _The colour vector induced by any $3$-edge-colouring of $H^{+}$
involves all three colours._

_Proof of Claim 2._ Consider the colour vector induced by a $3$-edge-colouring
of $H^{+}$. If there was a colour that does not appear in it, then the
corresponding colour class could be extended to a perfect matching of the
entire $G$ that covers the three uncovered edges of $C$. Consequently, $G$
could be covered with four perfect matchings, contrary to our assumption.
Claim 2 is proved.

There exist exactly fifteen colouring types involving all three colours; they
are listed as $\alpha_{1},\alpha_{2},\ldots,\alpha_{15}$ in the first column
of Table 1 following the lexicographic order. Let $\mathcal{A}$ denote the set
comprising all of them. We now specify three subsets of $\mathcal{A}$:

$\displaystyle\mathcal{B}$ $\displaystyle=\\{123132,121323,123213\\},$
$\displaystyle\mathcal{C}$
$\displaystyle=\\{112332,122133,123123,123321\\},\quad\text{ and}$
$\displaystyle\mathcal{P}$
$\displaystyle=\\{112233,112323,121233,121332,122313,122331,123231,123312\\}.$

Clearly, $\mathcal{B}$, $\mathcal{C}$, and $\mathcal{P}$ form a partition of
$\mathcal{A}$. The sets $\mathcal{C}$ and $\mathcal{P}$ have a straightforward
interpretation if we choose our graph $G$ to be the Petersen graph $Pg$ and
$C$ the hexagonal core of an arbitrary optimal $3$-array. In this case,
$\mathcal{C}$ and $\mathcal{P}$ are simply the sets of all colouring types
including all three colours that are admissible for $C^{+}$ and
$H^{+}=(Pg-V(C))^{+}$, respectively.

colouring type |  | contained in
---|---|---
$\alpha_{1}=112233$ |  | $\mathcal{P}$
$\alpha_{2}=112323$ |  | $\mathcal{P}$
$\alpha_{3}=112332$ |  | $\mathcal{C}$
$\alpha_{4}=121233$ |  | $\mathcal{P}$
$\alpha_{5}=121323$ |  | $\mathcal{B}$
$\alpha_{6}=121332$ |  | $\mathcal{P}$
$\alpha_{7}=122133$ |  | $\mathcal{C}$
$\alpha_{8}=122313$ |  | $\mathcal{P}$
$\alpha_{9}=122331$ |  | $\mathcal{P}$
$\alpha_{10}=123123$ |  | $\mathcal{C}$
$\alpha_{11}=123132$ |  | $\mathcal{B}$
$\alpha_{12}=123213$ |  | $\mathcal{B}$
$\alpha_{13}=123231$ |  | $\mathcal{P}$
$\alpha_{14}=123312$ |  | $\mathcal{P}$
$\alpha_{15}=123321$ |  | $\mathcal{C}$

Table 1. The fifteen colouring types involving all three colours.

Claim 3. _Every colouring type admissible for $H^{+}$ belongs to
$\mathcal{P}$._

_Proof of Claim 3._ To prove the claim it is sufficient to exclude the
existence of colourings of $H^{+}$ whose type belongs to
$\mathcal{B}\cup\mathcal{C}$. We first observe that $H^{+}$ cannot have a
colouring of any type from
$\mathcal{C}=\\{\alpha_{3},\alpha_{7},\alpha_{10},\alpha_{15}\\}$. Indeed, if
it had, then such a colouring could easily be extended to a $3$-edge-colouring
of the entire $G$. Since $G$ is a snark, this cannot happen. Thus it remains
to deal with colourings whose type belongs to
$\mathcal{B}=\\{\alpha_{5},\alpha_{11},\alpha_{12}\\}$.

Suppose that $H^{+}$ admits a colouring of type $\alpha_{5}=121323$. Take the
$(1,3)$-Kempe chain starting at $f_{0}$. It must terminate at $f_{2}$,
$f_{3}$, or $f_{5}$, and the corresponding Kempe switches yield the colour
vectors $323323$, $321123$, or $321321$, respectively. The first of them has a
missing colour, and therefore cannot occur, by Claim 2. The latter two have
the type that belongs to $\mathcal{C}$, which we have already excluded.
Therefore $H^{+}$ has no colouring of type type $\alpha_{5}$.

Next, consider the colouring type $\alpha_{11}=123132$. Consider the
$(2,3)$-Kempe chain starting at $f_{1}$. The chain necessarily terminates at
$f_{2}$, $f_{4}$, or $f_{5}$, and the corresponding switches yield the colour
vectors $132132$, $133122$, or $133133$, respectively. The first two colour
vectors have the type that belongs to $\mathcal{C}$, while the last one has a
missing colour. Hence, the colouring type $\alpha_{11}$ is also excluded.

Finally we deal with the colouring type $\alpha_{12}=123213$. This time we
consider the $(1,2)$-Kempe chain starting at $f_{0}$. Its terminal edge must
be one of $f_{1}$, $f_{3}$, or $f_{4}$, and the corresponding switches produce
the vectors $213213$, $223113$, or $223223$, respectively. Again, the first
two colour vectors have the type that belongs to $\mathcal{C}$, while last one
has a missing colour. The colouring type $\alpha_{12}$ is thus excluded as
well.

Summing up, we have shown that $H^{+}$ admits no colouring whose type belongs
to $\mathcal{B}\cup\mathcal{C}$. It follows that $H^{+}$ only admits
colourings whose type belongs to $\mathcal{P}$. Claim 3 is proved.

We continue with the proof by analysing the set $U=\\{u_{0},\ldots,u_{5}\\}$.
In general, the vertices $u_{0}$, $u_{1}$, …, $u_{5}$ need not be pairwise
distinct, and some of them may coincide. Clearly, it cannot happen that
$u_{j}=u_{j+1}$ for some index $j$, for otherwise $G$ would contain a triangle
$(u_{j}v_{j}v_{j+1})$, which is impossible because $G$ is cyclically $4$-edge-
connected. If $u_{j}=u_{j+2}$ for some index $j$, then $G$ contains a
quadrangle $(u_{j}v_{j}v_{j+1}v_{j+2})$ whose intersection with $C$ is a path
of length two. However, this contradicts Lemma 3.4. Thus, the only possibility
is that some of the pairs $u_{i}$ and $u_{i+3}$ coincide. Let $x$ be the
number of such pairs; clearly $x\in\\{0,1,2,3\\}$. We prove that $x=3$.

Figure 6. Constructing $H^{\sharp}$ from $H^{+}$.

Suppose to the contrary that $x\leq 2$. Without loss of generality, we may
assume that $u_{2}\neq u_{5}$. We now take the graph $H^{+}$ and create from
it a new cubic graph $H^{\sharp}$ as follows. First, we remove the edges
$f_{2}$ and $f_{5}$ and add an edge $e$ between $u_{2}$ and $u_{5}$. Then we
identify the endvertices $v_{0}$ and $v_{1}$ of $f_{0}$ and $f_{1}$ into a new
vertex $s$. Similarly, we identify the endvertices $v_{3}$ and $v_{4}$ of
$f_{3}$ and $f_{4}$ into a vertex $t$. Finally, we add an edge $f$ between $s$
and $t$; see Figure 6.

We prove that $H^{\sharp}$ is not $3$-edge-colourable. If $H^{\sharp}$ had a
$3$-edge-colouring, then such a colouring would result from a $3$-edge-
colouring $\sigma$ of $H^{+}$ whose colour type $\alpha=c_{0}c_{1}\ldots
c_{5}$ satisfies all of the following conditions:

  * (i)

$c_{0}\neq c_{1}$ ($\sigma$ is proper at $s$),

  * (ii)

$c_{3}\neq c_{4}$ ($\sigma$ is proper at $t$), and

  * (iii)

$c_{2}=c_{5}$ ($e$ is properly coloured).

Moreover, Claim 3 tells us that $\alpha\in\mathcal{P}$. However, by checking
the elements of $\mathcal{P}$ we see that the colouring types $\alpha_{1}$ and
$\alpha_{2}$ violate (i), $\alpha_{6}$ and $\alpha_{9}$ violate (ii), and
$\alpha_{4}$, $\alpha_{8}$, $\alpha_{13}$, and $\alpha_{14}$ violate (iii). In
other words, no element of $\mathcal{P}$ satisfies all the conditions
(i)-(iii), and therefore $H^{\sharp}$ admits no $3$-edge-colouring.

Observe that $H^{\sharp}-\\{e,f\\}$ is bipartite with bipartition
$\\{S\cup\\{s,t\\},(V(H)-S)\\}$. Since $H^{\sharp}$ is not $3$-edge-
colourable, from Theorem 4.4 we deduce that $H^{\sharp}$ must have a bridge,
say $b$. A simple counting argument shows that in $H^{\sharp}$ the bridge $b$
separates $e$ from $f$. Let $Q$ be the component of $H^{\sharp}-b$ containing
$e$. Now, $Q-e$ is a subgraph of $G$ separated from the rest of $G$ by the cut
$\delta_{G}(Q-e)=\\{b,f_{2},f_{5}\\}$. Since $Q$ has at least two vertices and
so does the other component of $G-\delta_{G}(Q-e)$, we conclude that
$\delta_{G}(Q-e)$ is a cycle-separating $3$-edge-cut in $G$. This contradicts
the assumption that $G$ is cyclically $4$-edge-connected, and proves that
$x=3$.

We have thus proved that $u_{0}=u_{3}$, $u_{1}=u_{4}$, and $u_{2}=u_{5}$.
Consider the subgraph $J\subseteq G$ induced by the set
$C\cup\\{u_{0},u_{1},u_{2}\\}$. Each of the vertices $u_{0}$, $u_{1}$, and
$u_{2}$ is $2$-valent in $J$, which means that $\delta_{G}(J)$ is a $3$-edge-
cut. As $G$ is cyclically $4$-edge-connected,
$G-(C\cup\\{u_{0},u_{1},u_{2}\\})$ must be a single vertex. Now it is
immediate that $G$ is isomorphic to the Petersen graph.

Summing up, we have proved that every cyclically $4$-edge-connected cubic
graph $G$ with $\mathrm{df}({G})=3$ and $\pi(G)\geq 5$ is isomorphic to the
Petersen graph, as required. This completes the proof. ∎

##  7\. Family of snarks with defect 3 and perfect matching index 5

The requirement of cyclic connectivity at least $4$ in Theorem 1.2 is
essential, because there exist infinitely many $3$-edge-connected snarks with
defect $3$ and perfect matching index $5$. They can be constructed as follows:

Take the Petersen graph $Pg$ and remove a vertex $v$ from it together with the
three incident edges, leaving a graph $P$ containing three $2$-valent
vertices. Further, take an arbitrary connected bipartite cubic graph on at
least four vertices, and similarly remove a vertex $u$, leaving a graph $B$
with tree $2$-valent vertices. Create a cubic graph $H$ by joining every
$2$-valent vertex of $P$ to a $2$-valent vertex of $B$. Clearly, the set $R$
consisting of the newly added edges is a cycle-separating $3$-edge-cut in $H$.
We claim that the graph $H$ has defect 3 and perfect matching index $5$.

We first observe that $\mathrm{df}({H})=3$. Parity Lemma implies that $P$ is
uncolourable, so $H$ is a snark, and therefore $\mathrm{df}({H})\geq 3$. Since
$Pg$ is vertex-transitive, one can choose an optimal array for $Pg$ in such a
way that its hexagonal core avoids the vertex $v$. As every bipartite graph is
$3$-edge-colourable, one can easily extend the $3$-array of $Pg$ to a
$3$-array of $H$ which retains the original core of $Pg$. Hence,
$\mathrm{df}({H})=3$.

Now we want to prove that $\pi(H)=5$. Suppose to the contrary that $\pi(H)\leq
4$. Then $H$ has a covering $\mathcal{C}=\\{M_{1},M_{2},M_{3},M_{4}\\}$ with
four perfect matchings. Since both $P$ and $B$ contain an odd number of
vertices, we conclude that each $M_{i}$ has an odd number of common edges with
$R$. Moreover, since each edge of $H$ is in at most two of the four perfect
matchings, the weights of edges in the edge cut $R$ are either $1,1,2$, or
$2,2,2$. The former possibility is excluded, because contracting $B$ to a
single vertex would produce a covering of $Pg$ with four perfect matchings,
contradicting the fact that $\pi(Pg)=5$. Therefore the weight of each edge in
$R$ equals $2$. Now, each vertex of $B$ is incident with precisely one edge of
weight $2$, including those in $R$. It follows that the simply covered edges
form a $2$-factor of $B$, say $F$. However, $B$ has an odd number of vertices,
so at least one circuit of $F$ is odd, which is impossible because $B$ is
bipartite. Hence, $\pi(H)\geq 5$, and from Theorem 1.1 we infer that
$\pi(H)=5$.

## Acknowledgements

This research was supported by the grant No. APVV-19-0308 of Slovak Research
and Development Agency. The first and the third author were partially
supported by the grant VEGA 2/0078/20 of Slovak Ministry of Education. The
second author was partially supported by the grant VEGA 1/0743/21, and the
fourth author was supported by the grant VEGA 1/0727/22.

The authors are grateful to Tomáš Kaiser for suggesting a shorter proof of
Proposition 4.3.

## References

  * [1] I. Allie, Oddness to resistance ratios in cubic graphs, Discrete Math. 342 (2019), 387–391.
  * [2] I. Allie, E. Máčajová, M. Škoviera, Snarks with resistance $n$ and flow resistance $2n$, Electron. J. Combin. 29 (2022), $\\#$P1.44.
  * [3] G. Brinkmann, J. Goedgebeur, J. Hägglund, K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013), 468–488.
  * [4] P. J. Cameron, A. G. Chetwynd, J. J. Watkins, Decomposition of snarks, J. Graph Theory 11 (1987), 13–19.
  * [5] F. Chen, G. Fan, Fulkerson-covers of hypohamiltonian graphs, Discrete Appl. Math. 186 (2015), 66–73.
  * [6] G. Fan, A. Raspaud, Fulkerson’s conjecture and circuit covers, J. Combin. Theory Ser. B 61 (1994), 133–138.
  * [7] M. A. Fiol, G. Mazzuoccolo, E. Steffen, Measures of edge-uncolorability of cubic graphs, Electron. J. Combin. 25 (2018), $\\#$P4.54.
  * [8] J.-L. Fouquet, J.-M. Vanherpe, On the perfect matching index of bridgeless cubic graphs, arXiv:0904.1296 [cs.DM], (2009).
  * [9] D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971), 16–194.
  * [10] R.-X. Hao, J. Niu, X. Wang, C.-Q. Zhang, T. Zhang, A note on Berge-Fulkerson coloring, Discrete Math. 309 (2009), 4235–4240.
  * [11] R.-X. Hao, C.-Q. Zhang, T. Zheng, Berge-Fulkerson coloring for $C_{(8)}$-linked graphs, J. Graph Theory 88 (2018), 46–60.
  * [12] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975), 221–239.
  * [13] L. Jin, E. Steffen, Petersen cores and the oddness of cubic graphs, J. Graph Theory 84 (2017), 109–120.
  * [14] L. Jin, E. Steffen, G. Mazzuoccolo, Cores, joins and the Fano-flow conjectures, Discuss. Math. Graph Theory 38, 165–175.
  * [15] J. Karabáš, E. Máčajová, R. Nedela, M. Škoviera, Girth, oddness, and colouring defect of snarks, Discrete Math. 345 (2022), 113040.
  * [16] J. Karabáš, E. Máčajová, R. Nedela, M. Škoviera, Cubic graphs with colouring defect $3$, manuscript.
  * [17] S. Liu, R.-X. Hao, C.-Q. Zhang, Rotation snark, Berge-Fulkerson conjecture and Catlin’s 4-flow reduction, Appl. Math. Comput. 410 (2021), 126441.
  * [18] R. Lukot’ka, E. Máčajová, J. Mazák, M. Škoviera, Small snarks with large oddness, Electron. J. Combin. 22 (2015), $\\#$P1.51.
  * [19] R. Lukot’ka, E. Rollová, Perfect matchings of regular bipartite graphs, J. Graph Theory 85+ (2017) 525–532.
  * [20] E. Máčajová, G. Mazzuoccolo, Reduction of the Berge-Fulkerson conjecture to cyclically $5$-edge-connected snarks, Proc. Amer. Math. Soc. 148 (2020), 464–4652.
  * [21] E. Máčajová, M. Škoviera, Cubic graphs that cannot be covered with four perfect matchings, J. Combin. Theory Ser. B 150 (2021), 144–176.
  * [22] P. Manuel, A. S. Shanthi, Berge-Fulkerson conjecture on certain snarks, Math. Comput. Sci. 9 (2015), 209–220.
  * [23] G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory 68 (2011), 125–128.
  * [24] R. Nedela, M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253–279.
  * [25] J. Plesník, Connectivity of regular graphs and the existence of $1$-factors, Mat. Časopis 22 (1972), 310–318.
  * [26] P. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London. Math. Soc. 38 (1979), 423–460.
  * [27] E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998), 183–203.
  * [28] E. Steffen, $1$-Factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015), 195–206.
  * [29] W. Sun, F. Wang, A class of cubic graphs satisfying Berge conjecture, Graphs Combin. 38 (2022), Art. No. 66.
  * [30] C. Thomassen, The Erdős-Pósa property for odd cycles in graphs of large connectivity, Combinatorica 21 (2001), 321–333.
  * [31] C. Thomassen, Y. Wu, C.-Q. Zhang, The $3$-flow conjecture, factors modulo $k$, and the $1$-$2$-$3$-conjecture, J. Combin. Theory Ser. B 121 (2016), 308–325.
  * [32] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111.