ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 277-298
https://doi.org/10.26493/1855-3974.1601.e75
(Also available at http://amc-journal.eu)
Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44*
*
Jan Goedgebeur
Department of Applied Mathematics, Computer Science & Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium and Computer Science Department, University ofMons, Place du Parc 20, 7000 Mons, Belgium
Department of Computer Science, Comenius University, 842 48 Bratislava, Slovakia Received 14 February 2018, accepted 22 September 2018, published online 6 January 2019
The family of snarks - connected bridgeless cubic graphs that cannot be 3-edge-colour-ed - is well-known as a potential source of counterexamples to several important and long-standing conjectures in graph theory. These include the cycle double cover conjecture, Tutte's 5-flow conjecture, Fulkerson's conjecture, and several others. One way of approaching these conjectures is through the study of structural properties of snarks and construction of small examples with given properties. In this paper we deal with the problem of determining the smallest order of a nontrivial snark (that is, one which is cyclically 4-edge-connected and has girth at least 5) of oddness at least 4. Using a combination of structural analysis with extensive computations we prove that the smallest order of a snark with oddness at least 4 and cyclic connectivity 4 is 44. Formerly it was known that such a snark must have at least 38 vertices and one such snark on 44 vertices was constructed by Lukot'ka, Mâcajovâ, Mazâk and Skoviera in 2015. The proof requires determining all cyclically 4-edge-connected snarks on 36 vertices, which extends the previously compiled list of all such snarks up to 34 vertices. As a by-product, we use this new list to test the validity of several conjectures where snarks can be smallest counterexamples.
Keywords: Cubic graph, cyclic connectivity, edge-colouring, snark, oddness, computation. Math. Subj. Class.: 05C15, 05C21, 05C30, 05C40, 05C75, 68R10
*The first author was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). The second and the third author were partially supported by VEGA 1/0876/16 and by APVV-15-0220. Most computations for this work were carried out using the Stevin Supercomputer Infrastructure at Ghent University.
E-mail addresses: jan.goedgebeur@ugent.be (Jan Goedgebeur), macajova@dcs.fmph.uniba.sk (Edita Macajova), skoviera@dcs.fmph.uniba.sk (Martin Skoviera)
Edita Mácajová, Martin Skoviera
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
278
Ars Math. Contemp. 16(2019)299-317
1 Introduction
Snarks are an interesting, important, but somewhat mysterious family of cubic graphs whose characteristic property is that their edges cannot be properly coloured with three colours. Very little is known about the nature of snarks because the reasons which cause the absence of 3-edge-colourability in cubic graphs are not well understood. Snarks are also difficult to find because almost all cubic graphs are hamiltonian and hence 3-edge-colourable [44]. On the other hand, deciding whether a cubic graph is 3-edge-colourable or not is NP-complete [26], implying that the family of snarks is sufficiently rich.
The importance of snarks resides mainly in the fact that many difficult conjectures in graph theory, such as Tutte's 5-flow conjecture or the cycle double cover conjecture, would be proved in general if they could be established for snarks [29, 30]. While most of these problems are trivial for 3-edge-colourable graphs, and exceedingly difficult for snarks in general, they often become tractable for snarks that are in a certain sense close to being 3-edge-colourable.
There exist a number of measures of uncolourability of cubic graphs (see [16] for a recent survey). Among them, the smallest number of odd circuits in a 2-factor of a cubic graph, known as oddness, has received the widest attention. Note that the oddness of a cubic graph is an even integer which equals zero precisely when the graph is 3-edge-colourable. It is known, for example, that the 5-flow conjecture and the Fan-Raspaud conjecture are true for cubic graphs of oddness at most two [30, 37], while the cycle double cover conjecture is known to hold for cubic graphs of oddness at most 4 [24, 27]. Snarks with large oddness thus still remain potential counterexamples to these conjectures and therefore merit further study.
Several authors have provided constructions of infinite families of snarks with increasing oddness, see, for example, [25, 33, 35, 49]. Most of them focus on snarks with cyclic
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 279
connectivity at least 4 and girth at least 5, because snarks that lack these two properties can be easily reduced to smaller snarks. We call such snarks nontrivial. All currently available constructions indicate that snarks of oddness greater than 2 are extremely rare. From [7, Observation 4.10] it follows that there exist no nontrivial snarks of oddness greater than 2 on up to 36 vertices. The smallest known example of a nontrivial snark with oddness at least 4 has 44 vertices and its oddness equals 4. It was constructed by Lukot'ka et al. in [35], superseding an earlier construction of Hagglund [25] on 46 vertices; it is shown in Figure 1 in a form different from the one displayed in [35]. In [35, Theorem 12] it is also shown that if we allow trivial snarks, the smallest one with oddness greater than 2 has 28 vertices and oddness 4. As explained in [22, 34], there are exactly three such snarks, one with cyclic connectivity 3 and two with cyclic connectivity 2. (The latter result rectifies the false claim made in [35] that there are only two snarks of oddness 4 on 28 vertices.)
The aim of the present paper is to prove the following result.
Theorem 1.1. The smallest number of vertices of a snark with cyclic connectivity 4 and oddness at least 4 is 44. The girth of each such snark is at least 5.
This theorem bridges the gap between the order 36 up to which all nontrivial snarks have been generated (and none of oddness greater than 2 was found [7]) and the order 44 where an example of oddness 4 has been constructed [35]. Since generating all nontrivial snarks beyond 36 vertices seems currently infeasible, it would be hardly possible to find a smallest nontrivial snark with oddness at least 4 by employing computational force alone. On the other hand, the current state-of-the-art in the area of snarks, with constructions significantly prevailing over structural theorems, does not provide sufficient tools for a purely theoretical proof of our theorem. Our proof is therefore an inevitable combination of structural analysis of snarks with computations.
The proof consists of two steps. First we prove that every snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices can be decomposed into two smaller cyclically 4-edge-connected snarks Gi and G2 by removing a cycle-separating 4-edge-cut, adding at most two vertices to each of the components, and by restoring 3-regularity. Conversely, every such snark arises from two smaller cyclically 4-edge-con-nected snarks Gi and G2 by the reverse process. In the second step of the proof we computationally verify that no combination of Gi and G2 can result in a cyclically 4-edge-connected snark of oddness at least 4 on fewer than 44 vertices. This requires checking all suitable pairs of cyclically 4-edge-connected snarks on up to 36 vertices, including those that contain 4-cycles. Such snarks have been previously generated only up to order 34 [7], which is why we had to additionally generate all cyclically 4-edge-connected snarks on 36 vertices containing a 4-cycle. This took about 80 CPU years and yielded exactly 404 899 916 cyclically 4-edge-connected snarks.
It is important to realise that Theorem 1.1 does not yet determine the order of a smallest nontrivial snark with oddness at least 4. The reason is that it does not exclude the existence of cyclically 5-connected snarks with oddness at least 4 on fewer than 44 vertices. However, the smallest currently known cyclically 5-edge-connected snark with oddness at least 4 has 76 vertices (see Steffen [49, Theorem 2.3]), which indicates that a cyclically 5-edge-connected snark with oddness at least 4 on fewer than 44 vertices either does not exist or will be very difficult to find.
Our paper is organised as follows. Section 2 provides the necessary background material for the proof of Theorem 1.1 and for the results that precede it, in particular for the
280
Ars Math. Contemp. 16(2019)299-317
decomposition theorems proved in Section 3. In Section 4 we employ these decomposition theorems to prove Theorem 1.1. We further discuss this theorem in Section 5 where we also pose two related problems. In the final section we report about the tests which we have performed on the set of all cyclically 4-edge-connected snarks of order 36 concerning the validity of several interesting conjectures in graph theory, such as the dominating cycle conjecture, the total colouring conjecture, and the Petersen colouring conjecture.
We will continue our investigation of the smallest snarks with oddness at least 4 and cyclic connectivity 4 in the sequel of this paper [23]. We will display a set of 31 such snarks, analyse their properties, and prove that they constitute the complete set of snarks with oddness at least 4 and cyclic connectivity 4 on 44 vertices.
2 Preliminaries
2.1	Graphs and multipoles
All graphs in this paper are finite. For the sake of completeness, we have to permit graphs containing multiple edges or loops, although these features will in most cases be excluded by the imposed connectivity or colouring restrictions.
Besides graphs we also consider graph-like structures, called multipoles, that may contain dangling edges and even isolated edges. Multipoles serve as a convenient tool for constructing larger graphs from smaller building blocks. They also naturally arise as a result of severing one or several edges of a graph, in particular edges forming an edge-cut. In this paper all multipoles will be cubic (3-valent).
Every edge of a multipole has two ends and each end can, but need not, be incident with a vertex. An edge which has both ends incident with a vertex is called proper. If one end of an edge is incident with a vertex and the other is not, then the edge is called a dangling edge and, if neither end of an edge is incident with a vertex, it is called an isolated edge. An end of an edge that is not incident with a vertex is called a semiedge. A multipole with k semiedges is called a k-pole. Two semiedges s and t of a multipole can be joined to produce an edge s * t connecting the end-vertices of the corresponding dangling edges. Given two k-poles M and N with semiedges si,..., sk and t1,... ,tk, respectively, we define their complete junction M * N to be the graph obtained by performing the junctions sj * tj for each i e {1,..., k}. A partial junction is defined in a similar way except that a proper subset of semiedges of M is joined to semiedges of N. Partial junctions can be used to construct larger multipoles from smaller ones. In either case, whenever a junction of two multipoles is to be performed, we assume that their semiedges are assigned a fixed order. For a more detailed formal development of concepts related to multipoles we refer the reader, for example, to [15, 36] or [13].
2.2	Cyclic connectivity
Let G be a connected graph. An edge-cut of a graph G, or just a cut for short, is any set S of edges of G such that G - S is disconnected. An edge-cut is said to be trivial if it consists of all edges incident with one vertex, and nontrivial otherwise. An important kind of an edge-cut is a cocycle, which arises by taking a set of vertices or an induced subgraph H of G and letting S to be the set SG (H) of all edges with exactly one end in H. We omit the subscript G whenever G is clear from the context.
An edge-cut is said to be cycle-separating if at least two components of G - S contain
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 281
cycles. We say that a connected graph G is cyclically k-edge-connected if no set of fewer than k edges is cycle-separating in G. The cyclic connectivity of G, denoted by Z(G), is the largest number k < ¡3(G), where ¡3(G) = | E(G) | - | V(G) | + 1 is the cycle rank of G, for which G is cyclically k-connected (cf. [41, 43]).
It is not difficult to see that for a cubic graph G with Z(G) < 3 the value Z(G) coincides with the usual vertex-connectivity or edge-connectivity of G. Thus cyclic connectivity in cubic graphs is a natural extension of the common versions of connectivity (which unlike cyclic connectivity are bounded above by 3). Another useful observation is that the value of cyclic connectivity remains invariant under subdivisions and adjoining new vertices of degree 1 .
The following well-known result [41, 43] relates Z(G) to the length of a shortest cycle in G, denoted by g(G) and called the girth of G.
Proposition 2.1. For every connected cubic graph G we have Z(G) < g(G).
Let us observe that in a connected cubic graph every edge-cut S consisting of independent edges is cycle-separating: indeed the minimum valency of G - S is 2, so each component of G - S contains a cycle. Conversely, a cycle-separating edge-cut of minimum size is easily seen to be independent; moreover, G - S has precisely two components, called cyclic parts or fragments. A fragment minimal under inclusion will be called an atom. A nontrivial atom is any atom different from a shortest cycle.
The following two propositions provide useful tools in handling cyclic connectivity. The first of them follows easily by mathematical induction. For the latter we refer the reader to [41, Proposition 4 and Theorem 11].
Lemma 2.2. Let H be a connected acyclic subgraph of a cubic graph separated from the rest by a k-edge-cut. Then H has k — 2 vertices.
Proposition 2.3. Let G be a connected cubic graph. The following statements hold:
(i)	Every fragment of G is connected, and every atom is 2-connected. Moreover, if Z (G) > 3, then every fragment is 2-connected.
(ii)	If A is a nontrivial atom of G, then Z (A) > Z (G)/2.
In the present paper we focus on cyclically 4-edge-connected cubic graphs, in particular on those with cyclic connectivity exactly 4. From the results mentioned earlier it follows that a cyclically 4-edge-connected cubic graph has no bridges and no 2-edge-cuts. Furthermore, every 3-edge-cut separates a single vertex, and every 4-edge-cut which is not cycle-separating consists of the four edges adjacent to some edge.
An important method of constructing cyclically 4-edge-connected cubic graphs from smaller ones applies the following operation which we call an I-extension. In a cubic graph G take two edges e and f, subdivide each of e and f with a new vertex ve and vf, respectively, and by add a new edge between ve and vf. The resulting graph, denoted by G(e, f) is said to be obtained by an I-extension across e and f. It is not difficult to see that if G is cyclically 4-edge-connected and e and f are non-adjacent edges of G, then so is G(e, f).
A well-known theorem of Fontet [19] and Wormald [51] states that all cyclically 4-edge-connected cubic graphs can be obtained from the complete graph K4 and the cube Q3 by repeatedly applying I-extensions to pairs of non-adjacent edges. However, I-extensions
282
Ars Math. Contemp. 16(2019)299-317
are also useful for constructing cubic graphs in general. For example, in [8] all connected cubic graphs up to 32 vertices have been generated by using I-extensions as main construction operation.
For more information on cyclic connectivity the reader may wish to consult [41]. 2.3 Edge-colourings
A k-edge-colouring of a graph G is amapping ^: E (G) ^ C where C is a set of k colours. If all pairs of adjacent edges receive distinct colours, ^ is said to be proper; otherwise it is called improper. Graphs with loops do not admit proper edge-colourings because of the self-adjacency of loops. Since we are mainly interested in proper colourings, the adjective "proper" will usually be dropped. For multipoles, edge-colourings are defined similarly; that is to say, each edge receives a colour irrespectively of the fact whether it is, or it is not, incident with a vertex.
The result of Shannon [47] implies that every loopless cubic graph, and hence every loopless cubic multipole, can be properly coloured with four colours, see also [32]. In the study of snarks it is often convenient to take the set of colours C to be the set Z2 x Z2 = {(0,0), (0,1), (1,0), (1,1)} where (0,0), (0,1), (1,0), and (1,1) are identified with 0, 1, 2, and 3, respectively. We say that a multipole is colourable if it admits a 3-edge-colouring and uncolourable otherwise. For a 3-edge-colouring of a cubic graph or a cubic multipole we use the colour-set C = {1, 2,3} because such a colouring is in fact a nowhere-zero Z2 x Z2-flow. This means that for every vertex v the sum of colours incident with v, the outflow at v, equals 0 in Z2 x Z2. The following fundamental result [5, 14] is a direct consequence of this fact.
Theorem 2.4 (Parity Lemma). Let M be a k-pole endowed with a proper 3-edge-colouring with colours 1, 2, and 3. If the set of all semi-edges contains k edges of colour i for i e {1,2,3}, then
ki = k2 = k3 = k (mod 2).
Now let M be a loopless cubic multipole that cannot be properly 3-edge-coloured. Then M has a proper 4-edge-colouring with colours from the set C = Z2 x Z2. Such a colouring will not be a Z2 x Z2 -flow anymore since every vertex incident with an edge coloured 0 will have a non-zero outflow. It is natural to require the colour 0 to be used as little as possible, that is, to require the set of edges coloured 0 to be the minimum-size colour class. Such a 4-edge-colouring will be called minimum. In a minimum 4-edge-colouring of M every edge e coloured 0 must be adjacent to edges of all three non-zero colours; in particular, e must be a proper edge. It follows that exactly one colour around e appears twice.
By summing the outflows at vertices incident with edges coloured 0 we obtain the following useful result due to Fouquet [20, Theorem 1] and Steffen [48, Lemma 2.2].
Theorem 2.5. Let ^ be a minimum 4-edge-colouring of a loopless cubic multipole M with m edges coloured 0, and for i e {1, 2,3} let mj denote the number of those edges coloured 0 that are adjacent to two edges coloured i. Then
mi = m-2 = m.3 = m (mod 2).
We finish the discussion of colourings with the definition of the standard recolouring tool, a Kempe chain. Let M be a cubic multipole whose edges have been properly coloured
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 283
with colours from the set {0,1,2,3} = Z2 x Z2. For any two distinct colours i, j £ {1, 2,3} we define an i-j-Kempe chain P to be a non-extendable walk that alternates the edges with colours i and j. Clearly, P is either an even circuit, or is a path that ends with either a semiedge or with a vertex incident with an edge coloured 0. It is easy to see that switching the colours i and j on P gives rise to a new proper 4-edge-colouring of M. Furthermore, if the original colouring was a minimum 4-edge-colouring, so is the new one.
2.4 Snarks
A snark is, essentially, a nontrivial cubic graph that has no 3-edge-colouring. Precise definitions vary depending on what is to be considered "nontrivial". In many papers, especially those dealing with snark constructions, snarks are required to be cyclically 4-edge-connected and have girth at least 5; see for example [12, 16]. However, in [9, 25] the girth requirement is dropped, demanding snarks to be cyclically 4-edge-connected but allowing them to have 4-cycles.
Another group of papers, especially those dealing with the structural analysis of snarks, adopts the widest possible definition of a snark, permitting all kinds of trivial features such as triangles, digons and even bridges; see, for example [11, 13,42]. In this paper, our usage of the term snark agrees with the latter group: we define a snark to be a connected cubic graph that cannot be 3-edge-coloured.
This paper deals with snarks that are far from being 3-edge-colourable. Two measures of uncolourability will be prominent in this paper. The oddness w(G) of a bridgeless cubic graph G is the smallest number of odd circuits in a 2-factor of G. The resistance p(G) of a cubic graph G is the smallest number of edges of G which have to be removed in order to obtain a colourable graph. Obviously, if G is colourable, then w(G) = p(G) = 0. If G is uncolourable, then both w(G) > 2 and p(G) > 2. Furthermore, p(G) < w(G) for every bridgeless cubic graph G.
The following lemma is due to Steffen [48].
Lemma 2.6. Let G be a bridgeless cubic graph. Then p(G) = 2 if and only if w(G) = 2.
One of the methods of constructing snarks from smaller ones uses I-extensions (cf. Subsection 2.2). The following result from [42] tells us when an I-extension of a snark is again a snark.
Lemma 2.7. Let G be a snark and e and f be distinct edges of G. Then G(e, f) is a snark if and only if the graph G — {e, f} is uncolourable.
Another method of constructing snarks is based on extending multipoles to cubic graphs, see [13]. If the multipole in question is uncolourable, it can be extended to a snark simply by restoring 3-regularity. We are therefore interested in extending colourable multipoles. For k > 2, we say that a k-pole M extends to a snark if there exists a colourable multipole N such that M * N is a snark. The graph M * N is called a snark extension of M.
Given a k-pole M with semiedges ei, e2,..., ek, we define its colouring set to be the following set of k-tuples:
Col(M) = {^(e1)^(e2)... ^(efc) : ^ is a 3-edge-colouring of M} .
Note that the set Col(M) depends on the ordering in which the semiedges are listed. We therefore implicitly assume that such an ordering is given. As the colourings "inside"
284
Ars Math. Contemp. 16(2019)299-317
a multipole can usually be ignored, we define two multipoles M and N to be colour-equivalent if Col(M) = Col(N).
Any colouring of a colourable multipole can be changed to a different colouring by permuting the set of colours. The particular colour of a semiedge is therefore not important, it is only important whether it equals or differs from the colour of any other semiedge. By saying this we actually define the type of a colouring ^ of a multipole M: it is the lexicographically smallest sequence of colours assigned to the semiedges of M which can be obtained from ^ by permuting the colours.
By the Parity Lemma (Theorem 2.4), each colouring of a 4-pole has one of the following types: 1111,1122,1212, and 1221. Observe that every colourable 4-pole admits at least two different types of colourings. Indeed, we can start with any colouring and switch the colours along an arbitrary Kempe chain to obtain a colouring of another type. Colourable 4-poles thus can have two, three, or four different types of colourings. Those attaining exactly two types are particularly important for the study of snarks; we call them colour-open 4-poles, as opposed to colour-closed multipoles discussed in more detail in [42].
The following result appears in [13].
Proposition 2.8. A colourable 4-pole extends to a snark if and only if it is colour-open.
A 4-pole M will be called isochromatic if its semiedges can be partitioned into two pairs such that in every colouring of M the semiedges within each pair are coloured with the same colour. A 4-pole M will be called heterochromatic of its semiedges can be partitioned into two pairs such that in every colouring of M the semiedges within each pair are coloured with distinct colours. The pairs of semiedges of an isochromatic or a heterochromatic 4-pole mentioned above will be called couples.
Note that the 4-pole C4 obtained from a 4-cycle by attaching one dangling edge to every vertex is colour-closed, and hence neither isochromatic nor heterochromatic. Indeed, with respect to a cyclic ordering of its semiedges it admits colourings of three types, namely 1111,1122, and 1221 (but not 1212). In particular, if a snark G contains a 4-cycle C, then, as is well-known, G - V(C) stays uncolourable.
The following two results are proved in [13]:
Proposition 2.9. Every colour-open 4-pole is either isochromatic or heterochromatic, but not both. Moreover, it is isochromatic if and only if it admits a colouring of type 1111.
Proposition 2.10. Every colour-open 4-pole can be extended to a snark by adding at most two vertices, and such an extension is unique. A heterochromatic multipole extends by joining the semiedges within each couple, that is, by adding no new vertex. An isochro-matic multipole extends by attaching the semiedges ofeach couple to a new vertex, and by connecting these two vertices with a new edge.
Colour-open 4-poles can be combined to form larger 4-poles from smaller ones by employing partial junctions: we take two 4-poles M and N, choose two semiedges in each of them, and perform the individual junctions. In general, such a junction need not respect the structure of the couples of the 4-poles participating in the operation. In this manner it may happen that, for example, a partial junction of two heterochromatic 4-poles results in an isochromatic dipole or in a heterochromatic dipole. In Theorem 3.5, one of our decomposition theorems, partial junctions of 4-poles will occur in the reverse direction.
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 285
3 Decomposition theorems
The aim of this section is to show that every snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices can be decomposed into two smaller cyclically 4-edge-connected snarks G1 and G2 by removing a cycle-separating 4-edge-cut, adding at most two vertices to each of the components, and by restoring 3-regularity. This will be proved in two steps - Theorem 3.3 and Theorem 3.5.
Theorem 3.3 is a decomposition theorem for cyclically 4-edge-connected cubic graphs proved in 1988 by Andersen et al. [2, Lemma 7]. Roughly speaking, it states that every cubic graph G whose cyclic connectivity equals 4 can be decomposed into two smaller cyclically 4-edge-connected cubic graphs Gi and G2 by removing a cycle-separating 4-edge-cut, adding two vertices to each of the components, and by restoring 3-regularity. Our proof is different from the one in [2] and provides useful insights into the problem. For instance, it offers the possibility to determine conditions under which it is feasible to extend a 4-pole to a cyclically 4-edge-connected cubic graph by adding two isolated edges rather than by adding two new vertices.
Theorem 3.5 deals with a particular situation where the cyclically 4-edge-connected cubic graph G in question is a snark. As explained in the previous section, every snark containing a cycle-separating 4-edge-cut that leaves a colour-open component can be decomposed into two smaller snarks Gi and G2 by removing the cut, adding at most two vertices to each of the components, and by restoring 3-regularity. Unfortunately, G1 or G2 are not guaranteed to be cyclically 4-edge-connected because snark extensions forced by the colourings need not coincide with those forced by the cyclic connectivity (see Example 3.1 below). Moreover, Proposition 2.10 suggests that restoring 3-regularity by adding no new vertices, that is, by joining pairs of the four 2-valent vertices to each other in one of the components, may be necessary in order for G1 or G2 to be a snark. If this is the case, Theorem 3.3 cannot be applied. Nevertheless, Theorem 3.5 shows that if G is a smallest nontrivial snark with oddness at least 4, then we can form G1 and G2 in such a way that they indeed will be cyclically 4-edge-connected snarks.
Example 3.1. We give an example of a cyclically 4-edge-connected snark in which a decomposition along a given cycle-separating 4-edge-cut forces one of the resulting smaller snarks to have cyclic connectivity smaller than 4. To construct such a snark take the Pe-tersen graph and form a 4-pole H of order 10 by severing two non-adjacent edges and a 4-pole I of order 8 by removing two adjacent vertices. It is easy to see that H is heterochro-matic with couples being formed by the semiedges obtained from the same edge, and I is isochromatic with couples formed by the semiedges formerly incident with the same vertex. Let us create a cubic graph G by arranging two copies of H and one copy of I into a cycle, and by performing junctions that respect the structure of the couples. The partial junction of two copies of H contained in G, denoted by H2, is again a heterochromatic 4-pole, so G is a junction of an isochromatic 4-pole I with a heterochromatic 4-pole, and therefore a snark. Furthermore, the cyclic connectivity of G equals 4. Let us decompose G by removing from G the 4-edge-cut S separating I from H2 and by completing each of the components to a snark. Proposition 2.10 implies that I can be completed to a copy G' of the Petersen graph while H2 extends to a snark G'' of order 20 by joining the semiedges within each couple, that is, by adding no new vertex. The same Proposition states that the decomposition of G into G' and G'' is uniquely determined by S. However, G'' has a cycle-separating 2-edge-cut connecting the two copies of H contained in it. Therefore the
286
Ars Math. Contemp. 16 (2019) 277-298
low connectivity of G" is unavoidable.
We proceed to Theorem 3.3. It requires one auxiliary result about comparable cuts. Let S and T be two edge-cuts in a graph G. Let us denote the two components of G - S by Hi and H2 and those of G - T by K and K2. The cuts S and T are called comparable if Hi C Kj or Kj C Hi for some i, j G {1,2}.
Lemma 3.2. Leí G be a cyclically 4-edge-connected cubic graph and let K be a component arising from the removal of a cycle-separating 4-edge-cut from G. Then any two nontrivial 2-edge-cuts in K are comparable, or K is a 4-cycle.
Proof. Let S be the cycle-separating 4-edge-cut that separates K from the rest of G, and let A = {ai, a2, a3, a4} be the set of the vertices of K incident with an edge from S. Since S is independent, the vertices of A are pairwise distinct. Proposition 2.3 (i) implies that K is 2-connected. It follows that for every nontrivial 2-edge-cut Q in K the graph K - Q consists of two components, each containing exactly two vertices of A.
Let R and T be two nontrivial 2-edge-cuts in K. Denote the components of K - R by Xi and X2, and those of K - T by Yi and Y2. Observe that the subgraphs Xi n Yj for i, j G {1, 2} need not all be non-empty. Let a be the number of edges between Xi n Yi and Xi n Y2, b the number of edges between Xi n Yi and X2 n Y2, c the number of edges between Xi n Yi and X2 n Yi, d the number of edges between Xi n Y2 and X2 n Yi, e the number of edges between X2 n Yi to X2 n Y2, and finally f the number of edges between Xi n Y2 and X2 n Y2; see Figure 2.
Figure 2: Crossing edge-cuts R and T.
If at least one of the sets Xi n Y1; Xi n Y2, X2 n Y1; and X2 n Y2 is empty, then the definition of comparable cuts directly implies that the cuts R and T are comparable, as required. Thus we can assume that all the subgraphs X¿ n Y are nonempty. Our aim is to show that in this case K is a 4-cycle. We start by showing that each of the subgraphs X1 n Y1, X1 n Y2, X2 n Y1, and X2 n Y2 contains exactly one element of A. Suppose that one of them, say X1 n Y1, contains no vertex from A. Since both R and T separate
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 287
the vertices from A in such a way that both components contain two vertices from A, we deduce that both X1 n Y2 and X2 n Y1 contain two vertices from A each, while X2 n Y2 contains no vertex from A. Now |SK (X1 n Y1)| = a + b + c > 3, because G has no bridges and no 2-edge-cuts. Further, since X1 n Y2 contains two vertices from A and G is cyclically 4-edge-connected, we see that |SK(X1 n Y2) | = a + d + f > 2. However, R is a 2-cut, so b + c + d + f = 2. Therefore 2a > 3 and hence a > 2. Similarly, e > 2. But then |T| > a + e > 4, which contradicts the fact that T is a 2-edge-cut. Thus all the subgraphs Xj n Yj contain an element of A, which in turn implies that each Xj n Xj contains exactly one vertex from A.
To finish the proof we show that a = c = e = f =1 and b = d = 0. Suppose that a = 2. Since T is a 2-edge-cut, we have that b = d = e = 0. Now c + d + e > 2 and b + e + f > 2 because G is 3-edge-connected, so c > 2 and f > 2, and hence |R| > c + f > 4, a contradiction. Thus a < 1. Similarly, we can derive that c < 1, e < 1, and f < 1. If b = 2, then a = c = d = e = f = 0 implying that G has a bridge, which is absurd. Hence b < 1 and similarly d < 1. Suppose that a = 0. As G is 3-edge-connected, we have 2 < a + b + c = b + c < 2 and similarly 2 < a + d + f = d + f < 2. It follows that that b = c = d = f = 1 and hence |R| = b + c + d + f = 4, which contradicts the fact that R is a 2-cut. Therefore a =1 and similarly c = e = f =1, which also implies that b = d = 0. Finally, every subgraph Xj n Yj has |SG(Xj n Yj)| = 3, so Xj n Yj is acyclic and therefore, by Lemma 2.2, a single vertex. In other words, K is a 4-cycle. This completes the proof.	□
We are ready to prove the decomposition theorem of Andresen et al. [2].
Theorem 3.3. Let G be a cyclically 4-edge-connected cubic graph with a cycle-separating 4-edge-cut whose removal leaves components G1 and G2. Then each of G1 and G2 can be extended to a cyclically 4-edge-connected cubic graph by adding two adjacent vertices and restoring 3-regularity.
Proof. It suffices to prove the statement for G1. If G1 is a 4-cycle, we can easily extend it to the complete bipartite graph K3 3 which is cyclically 4-edge-connected, as required. We therefore assume that G1 is not a 4-cycle. Let A = {a1, a2, a3, a4} be the set of vertices of G1 incident with an edge of Sg(G1). By Lemma 3.2, every 2-edge-cut in G1 separates the vertices of A into the same two 2-element sets, say {a1, a2} from {a3, a4}. We extend G1 to a cyclically 4-edge-connected cubic graph G1 as follows. Let us take two new vertices x1 and x2 and construct G1 from G1 by adding to G1 the edges x1x2, x1a1, x1a3, x2a2,
X\	x2
Figure 3: Extending G1 to ¿?1.
288
Ars Math. Contemp. 16(2019)299-317
and x2a4, see Figure 3. We now verify that Gi is indeed cyclically 4-edge-connected.
Suppose to the contrary that G1 is not cyclically 4-edge-connected. Then G1 has a minimum-size cycle-separating edge-cut F such that |F| < 4. Let H1 and H2 be the components of G1 - F. The cut F cannot consist entirely of edges of G1 U ¿g(G1) for otherwise F would be a cycle-separating edge-cut of G of size smaller than 4. Therefore the edge x1x2 is contained in F. Since F is an independent cut, the edges x1a1, x1a3, x2a2, and x2a4 do not belong to F. This in turn implies that a1 and a3 belong to one component of G1 - F while a2 and a4 belong to the other component of G1 - F; without loss of generality, let a1 and a3 belong to H1. Since G1 contains no bridge, there exist edges e1 and e2 in G1 such that F = {x1x2, e1, e2}. But then {e1, e2} is a 2-edge cut in G1 that separates the set {a1, a3} from {a2, a4}, which is a contradiction. This completes the proof.	□
Before proving the second main result of this section we need the following fact.
Proposition 3.4. Let G be a cubic graph with a cycle-separating 4-edge-cut whose removal leaves components G1 and G2. If both G1 and G2 are 3-edge-colourable, then w(G) < 2.
Proof. Assume that both G1 and G2 are 3-edge-colourable. If G is 3-edge-colourable, then w(G) = 0. Therefore we may assume that G is not 3-edge-colourable. In this situation G1 admits two types of colourings and G2 admits the other two types of colourings. One of them, say G1 has a colouring of the type 1111; by Proposition 2.9, G1 is isochromatic and G2 is heterochromatic. Parity Lemma (Theorem 2.4) implies that if we take an arbitrary 3-edge-colouring of G2, then exactly two colours occur on the dangling edges of G2. Let e and f be any two of the dangling edges that receive the same colour. Then, after permuting the colours in G1, if necessary, and can be easily combined to a 3-edge-colouring of G - {e, f}. This shows that p(G) = 2 and therefore w(G) = 2.	□
Now we are in position to prove our second decomposition theorem.
Theorem 3.5. Let G be a snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices. Then G contains a cycle-separating 4-edge-cut S such that both components of G - S can be extended to a cyclically 4-edge-connected snark by adding at most two vertices.
In fact, we prove the following stronger and more detailed result which will also be needed in our next paper [23].
Theorem 3.6. Let G be a snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices. Let S be a cycle-separating 4-edge-cut in G whose removal leaves components G1 and G2. Then, up to permutation of the index set {1,2}, exactly one of the following occurs.
(i)	Both G1 and G2 are uncolourable, in which case each of them can be extended to a cyclically 4-edge-connected snark by adding two vertices.
(ii)	G1 is uncolourable and G2 is heterochromatic, in which case G1 can be extended to a cyclically 4-edge-connected snark by adding two vertices, and G2 can be extended to a cyclically 4-edge-connected snark by adding two isolated edges.
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 289
(iii) Gi is uncolourable and G2 is isochromatic, in which case Gi can be extended to a cyclically 4-edge-connected snark by adding two vertices, and G2 can be extended to a cyclically 4-edge-connected snark by adding two vertices, except possibly Z (G2) = 2. In the latter case, G2 is a partial junction of two colour-open 4-poles, which may be isochromatic or heterochromatic in any combination.
Proof. Let G be a snark with w(G) > 4, Z(G) = 4, and with minimum number of vertices. Let S = {si, s2, s3, s4} be an arbitrary fixed cycle-separating 4-edge-cut in G, and let Gi and G2 be the components of G - S. According to Proposition 3.4, at least one of Gi and G2 is uncolourable. If both Gi and G2 are uncolourable, we can extend each of them to a cyclically 4-edge-connected snark by applying Theorem 3.3, establishing (i). For the rest of the proof we may therefore assume that G2 is colourable and Gi is not. Again, Gi can be extended to a cyclically 4-edge-connected snark by Theorem 3.3. Let Gi be an extension of Gi to a cyclically 4-edge-connected snark by adding two adjacent vertices yi and y2 according to Theorem 3.3. Without loss of generality we may assume that the vertex yi is incident with the edges si and s2 while y2 is incident with s3 and s4.
As regards G2, we prove that either (ii) or (iii) holds. Our first step in this direction is showing that G2 can be extended to a snark. In view of Proposition 2.8, this amounts to verifying that G2 is colour-open.
Claim 1. The 4-pole G2 is colour-open.
Proof of Claim 1. Suppose to the contrary that G2 is not colour-open. This means that it has at least three types of colourings. Since G is a smallest cyclically 4-edge-connected snark with oddness at least 4 and Gi is a cyclically 4-edge-connected snark with fewer vertices than G, we infer that w(Gi) = 2. By Lemma 2.6, there exist two nonadjacent edges ei and e2 in Gi such that Gi - {ei, e2} is colourable. Equivalently, by Lemma 2.7, the cubic graph Gi(ei, e2) is colourable.
We claim that the edge yiy2 is one of ei and e2. Suppose not. Then both ei and e2 have at least one end-vertex in Gi. As mentioned, ¿?i(ei, e2) is a colourable cubic graph. Hence Gi(ei, e2) is a colourable 4-pole, and therefore it has at least two types of colourings. Since G2 has at least three of the four types, both Gi(ei, e2) and G2 admit colourings of the same type. These colourings can be combined into a colouring of G(ei, e2), implying that G - {ei, e2} is also colourable. However, from Lemma 2.6 we get that w(G) = 2, which is a contradiction proving that one of ei and e2 coincides with yiy2.
Assuming that yiy2 = ei, let us consider a minimum 4-edge-colouring of Gi where ei and e2 are the only edges of Gi coloured 0. Theorem 2.5 implies that there exist a unique non-zero colour that is repeated at both ei and e2. Without loss of generality we may assume that the repeated colour is 1 and that ^i(si) = ^(s3) = 1, ^i(s2) = 2, and ^i(s4) = 3. In this situation, G2 cannot have a colouring of type 1212 for otherwise we could combine this colouring with to produce a 3-edge-colouring of G - {e2, s4}, which is impossible since w(G) > 4. Therefore G2 has colourings of all the remaining three types 1111, 1122, and 1221.
Consider the 1-2-Kempe chain P in Gi with respect to the colouring beginning at the vertex y2. Clearly, the other end of P must be the end-vertex of e2 incident with edges of colours 1, 3, and 0. If P does not pass through the vertex yi, we switch the colours on P producing a 4-edge-colouring ^i of Gi where ^'i(si) = 1, ^i(s2) = ^i(s3) = 2, and ^i(s4) = 3. However, ^i can be combined with a colouring of G2 of type 1221
290
Ars Math. Contemp. 16(2019)299-317
to obtain a 3-edge-colouring of G — {e2, s4}, which is impossible since w(G) > 4. If P passes through y, we switch the colours only on the segment P0 between y2 and y, producing an improper colouring of G1 with y1 being its only faulty vertex. Depending on whether P0 ends with an edge coloured 1 or 2 we get 4>'{(s1) = 4>1(s2) = 4>1(s3) = 2 and (S4) = 3, or (s 1) = ^"(s2) = 1, 4>"(S3) = 2, and (s4) = 3. In the latter case we can combine with a colouring of G2 of type 1122, producing a 3-edge-colouring of G — {e2, s4}. In the former case we first interchange the colours 1 and 2 on G 1 and then combine the resulting colouring with a colouring of G2 of type 1111, again producing a 3-edge-colouring of G — {e2, s4}. Since w(G) > 4, in both cases we have reached a contradiction. This establishes Claim 1.	□
Proposition 2.10 now implies that G2 can be extended to a snark G2 by adding at most two vertices. Recall that such an extension is unique up to isomorphism and depends only on whether G2 is isochromatic or heterochromatic. We discuss these two cases separately.
Case 1. G2 is isochromatic. First note that in this case G2 arises from G2 by adding two new vertices x 1 and x2 joined by an edge and by attaching each of the new vertices to the semiedges in the same couple. From Proposition 2.3 (i) we get that Z(G2) > 2. If Z(G2) > 4, then the same obviously holds for G2. Assume that Z(G2) = 3, and let A denote the set of end-vertices in G2 of the edges of the edge-cut S. Note that |A| = 4 because S is independent. Since Z(G) = 4, every cycle separating 3-edge-cut R in G2 has the property that each component of G2 — R contains at least one vertex from A. This readily implies that Z (G2) > 4 and establishes the statement (iii) whenever Z (G2) > 3. It remains to consider the case where Z(G2) = 2. Let U be a cycle-separating 2-edge-cut in G2 and let Q 1 and Q2 be the components of G2 — U. Since G is cyclically 4-edge-connected, each Qj contains exactly two vertices from A and thus both Q 1 and Q2 are 4-poles. Each Qj is colourable because any 3-edge-colouring of G2 provides one for Qj. Furthermore, each Qj is colour-open, because G2 and hence also Qj has an extension to G2. Thus G2 is a partial junction of two colour-open 4-poles. It is not difficult to show that an isochromatic 4-pole can arise from a partial junction of any combination of isochromatic and heterochromatic 4-poles, as claimed.
Case 2. G2 is heterochromatic. In this case G2 arises from a snark by severing two independent edges. Suppose to the contrary that G2 is not cyclically 4-edge-connected. Then G2 has at least twelve vertices, because there is only one 2-edge-connected snark of order less than twelve - the Petersen graph - and its cyclic connectivity equals 5. Let us take a heterochromatic 4-pole H of order 10 obtained from the Petersen graph and substitute G2 in G with H, creating a new cubic graph G'. Clearly, G' is a snark of order smaller than G. To derive a final contradiction with the minimality of G we show that G' is cyclically 4-edge-connected and has oddness at least 4.
Claim 2. w(G') > 4.
Proof of Claim 2. Suppose to the contrary that w(G') < 4. Since G 1 is uncolourable and G 1 C G', we infer that w(G') = 2 which in turn implies that p(G') = 2. Therefore there exist edges e 1 and e2 in G' such that G' — {e 1; e2} is colourable. In other words, G' has a minimum 4-edge-colouring ^ where e 1 and e2 are the only edges of G' coloured 0.
Since G is uncolourable, at least one of e and e2 must have both end-vertices in G . Without loss of generality assume that at e has both end-vertices in G . If e2 had at least
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 291
one end-vertex in Gi, we could take a 3-edge-colouring of G' - jei, e2}, remove H and reinstate G2 coloured in such a way that the edges in S -{ e2} receive the same colours from G2 as they did from H; this is possible since G2 and H are colour-equivalent. However, in this way we would produce a 3-edge-colouring of G — {e1, e2}, contrary to the assumption that w(G) = 4. Therefore e2 has both ends in H.
Since H is heterochromatic, the edges of S can be partitioned into couples such that for every 3-edge-colouring of H the colours of both edges within a couple are always different. Let {s», Sj} and {sk, s;} be the couples of H. Further, since ^ is a minimum 4-edge-colouring of G', all three non-zero colours are present on the edges adjacent to each of e», one of the colours being represented twice. By Theorem 2.5, the same colour occurs twice at both e1 and e2, say colour 1. If we regard ^ as a Z2 x Z2-valuation and sum the outflows from vertices of G1 we see that the flow through S equals ^(s1) + ^(s2) + ^(s3) + ^(s4) = 1. Hence, the distribution of colours in the couples of S, the set {{^(sj), -0(sj)}, {^(sfc), ^(s;)}}, must have one of the following four forms:
D1 = {{1,1}, {2, 3}},
D = {{1, 2}, {1, 3}},
D3 = {{2, 2}, {2, 3}},
D = {{2, 3}, {3, 3}}.
We now concentrate on the restriction of ^ to G1 and show that it can be modified to a 4-edge-colouring A of G1 with distribution either D2 or D3. If the colouring ^ of G' has distribution D4, we can simply interchange the colours 2 and 3 to obtain the distribution D3. Assume that ^ has distribution D1. Let us consider the unique end-vertex u of e1 in G1 such that the edges incident with u receive colours 1, 3, and 0 from The 1-2-Kempe chain P starting at u ends with a vertex incident with e2, which means that P traverses S. Let s be the first edge of S that belongs to P. If ^(s) = 1, then the desired 4-edge-colouring A of G1 with distribution D2 can be obtained by the Kempe switch on the segment of P that ends with s and by a subsequent permutation of colours interchanging 1 and 2. If ^(s) = 2, then a 4-edge-colouring of G1 with distribution D3 can be obtained similarly. In both cases, e1 is the only edge coloured 0 under A.
If A has distribution D2, then A and a 3-edge-colouring of H of type 1212 can be combined to a 3-edge-colouring of G' — {e1, s;}. However, as observed earlier, by removing H and reinstating G2 we could produce a 3-edge-colouring of G — {e1, s;}, which is impossible because w(G) > 4. If A has distribution D3, we can similarly combine A with a 3-edge-colouring of H of type 1221 to a 3-edge-colouring of G' — {e1, sj} which is impossible for the same reason. This contradiction completes the proof of Claim 2. □
Claim 3. Z(G') = 4.
Proof of Claim 3. Suppose to the contrary that Z (G') < 4. Let S' be a minimum size cycle-separating edge-cut in G'. If all the edges of S' had at least one end vertex in G1, then S' would be a cycle-separating cut also in G, which is impossible. Therefore at least one edge of S' has both ends in H, which means that S' intersects H. Since H is connected, we conclude that S'H = S' n E(H) is an edge-cut of H. Note that S'H is an independent set of edges, so S'H must be a cycle-separating edge-cut in H. Recall, however, that H arises from the Petersen graph by severing two independent edges e and f. It follows that S'H U {e, f} is a cycle-separating edge-cut in the Petersen graph. Hence, |SH U {e, f }| > 5,
292
Ars Math. Contemp. 16(2019)299-317
and consequently 3 < |SH| < |S'| < 3. This shows that S'H = S' and therefore S' is completely contained in H; in particular S' n S = 0. Because S' is an edge-cut of the entire G', all the edges of S must join Gi to the same component of H - S'. On the other hand, the Petersen graph is cyclically 5-edge-connected, therefore both e and f have end-vertices in different components of H - S'. The way how G' was constructed from G now implies that the set of end-vertices of S in H coincides with the set of end-vertices of e and f. Therefore S has an end-vertex in each component of H - S', contradicting the previous observation. This contradiction establishes Claim 3.	□
Claim 2 and Claim 3 combined provide a final contradiction with the choice of G, which concludes the proof.	□
We proceed to proving our second decomposition theorem.
Proof of Theorem 3.5. Let G be a snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices. If G contains a cycle-separating 4-edge-cut whose removal leaves either two uncolourable components or one uncolourable component and one hete-rochromatic component, then the conclusion follows directly from Theorem 3.6 (i) or (ii), respectively. Otherwise one of the components is uncolourable and the other one, denoted by G2, is isochromatic. In this case, G2 contains a subgraph K which is an atom, possibly K = G2. Clearly, K is colourable and SG(K) is a cycle-separating 4-edge-cut. If K is heterochromatic, then the conclusion again follows from Theorem 3.6 (ii). Therefore we may assume that K is isochromatic. Since 4 = Z(G) < 5 < g(G), we see that K is a nontrivial atom and from Proposition 2.3 (ii) we infer that Z(K) > 3. Applying statement (iii) of Theorem 3.6 with S = SG (K) we finally get the desired result.	□
4 Main result
We are now ready to prove our main result.
Theorem 1.1. The smallest number of vertices of a snark with cyclic connectivity 4 and oddness at least 4 is 44. The girth of each such snark is at least 5.
Proof. Let G be a snark with oddness at least 4, cyclic connectivity 4, and minimum order. We first prove that G has girth at least 5. By Proposition 2.1, the girth of G is at least 4. Suppose to the contrary that G contains a 4-cycle C, and let S be the edge-cut separating C from the rest of G. Since S is cycle-separating, it has to satisfy one of the statements (i) — (iii) of Theorem 3.6. In the notation of Theorem 3.6, C necessarily plays the role of G2, because it is colourable. In particular, S does not satisfy (i). However, S satisfies neither (ii) because G2 is not heterochromatic, nor (iii) since G2 is not isochromatic. Thus we have reached a contradiction proving that the girth of G is at least 5.
In Figure 1 we have displayed a snark with oddness at least 4, cyclic connectivity 4 on 44 vertices. It remains to show that there are no snarks of oddness at least 4 and cyclic connectivity 4 with fewer than 44 vertices.
Our main tool is Theorem 3.5. It implies that every snark with oddness at least 4, cyclic connectivity 4, and minimum number of vertices can be obtained from two smaller cyclically 4-edge-connected snarks G1 and G2 by the following process:
• Form a 4-pole H from each Gj by either removing two adjacent vertices or two nonadjacent edges and by retaining the dangling edges.
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 293
• Construct a cubic graph G by identifying the dangling edges of Hi with those of H2 after possibly applying a permutation to the dangling edges of Hi or H2.
Any graph G obtained in this manner will be called a 4-join of Gi and G2. Note that the well-known operation of a dot product of snarks [1, 28] is a special case of a 4-join.
We proceed to proving that every snark with cyclic connectivity 4 on at most 42 vertices has oddness 2. If G is a snark with cyclic connectivity 4 on at most 42 vertices, then by Theorem 3.5 it contains a cycle-separating 4-edge-cut S such that both components Ki and K2 of G - S can be extended to snarks Gi and G2, respectively, by adding at most two vertices; in other words, G is a 4-join of Gi and G2. Clearly, |V(Ki)| + |V(K2)| = |V(G)| < 42. Assuming that |V(Ki)| < |V(K2)| we see that |V(Ki)| > 8, because the smallest cyclically 4-edge-connected snark has 10 vertices, and hence |V(K2)| < 34. Therefore both Gi and G2 have order at least 10 and at most 36.
Let Sn denote the set of all pairwise non-isomorphic cyclically 4-edge-connected snarks of order not exceeding n. To finish the proof it remains to show that every 4-join of two snarks from S36 with at most 42 vertices has oddness 2. Unfortunately, verification of this statement in a purely theoretical way is far beyond currently available methods. The final step of our proof has been therefore performed by a computer.
We have written a program which applies a 4-join in all possible ways to two given input graphs and have applied this program to the complete list of snarks from the set S36. More specifically, given an arbitrary pair of input graphs, the program removes in all possible ways either two adjacent vertices or two nonadjacent edges from each of the graphs (retaining the dangling edges) and then identifies the dangling edges from the first graph in the pair with the dangling edges of the second graph, again in all possible (i.e., 4! = 24) ways. We also use the nauty library [39, 40] to determine the orbits of edges and edge pairs in the input graphs, so the program only removes two adjacent vertices or two nonadjacent edges once from every orbit of edges or edge pairs, respectively. The resulting graphs can still contain isomorphic copies, therefore we also use nauty to compute a canonical labelling of the graphs and remove the isomorphic copies.
Until now, only the set S34 has been known; it was determined by Brinkmann, Häg-glund, Markström, and the first author [7] in 2013 and was shown to contain exactly 27 205 766 snarks. Using the program snarkhunter [7, 8] we have been able to generate all cyclically 4-edge-connected snarks on 36 vertices, thereby completing the determination of S36. This took about 80 CPU years and yielded exactly 404 899 916 such graphs. The size of S36 thus totals to 432 105 682 graphs. (The new list of snarks can be downloaded from the House of Graphs [6] at http://hog.grinvin.org/Snarks.)
Finally, we have performed all possible 4-joins of two snarks from S36 that produce a snark with at most 42 vertices and checked their oddness. This computation required approximately 75 CPU days. We have used two independent programs to compute the oddness of the resulting graphs (the source code of these programs can be obtained from [21]) and in each case the results of both programs were in complete agreement. No snark of oddness greater than 2 among them was found, which completes the proof of Theorem 1.1. □
5 Remarks and open problems
We have applied the 4-join operation to all valid pairs of snarks from S36 to construct cyclically 4-edge-connected snarks on 44 vertices and checked their oddness. In this manner we have produced 31 cyclically 4-edge-connected snarks of oddness 4, including the one from
294
Ars Math. Contemp. 16(2019)299-317
Figure 1, all of them having girth 5. The most symmetric of them is shown in Figure 4. We will describe and analyse these 31 snarks in the sequel of this paper [23], where we also prove that they constitute a complete list of all snarks with oddness at least 4, cyclic connectivity 4, and minimum number of vertices.
As we have already mentioned in Introduction (Section 1), Theorem 1.1 does not yet determine the smallest order of a nontrivial snark with oddness 4, because there might exist snarks with oddness at least 4 of order 38, 40, or 42 with cyclic connectivity greater than 4. Furthermore, it is not immediately clear why a snark G with w (G) > m and minimum order should have oddness exactly m. This situation suggests two natural problems which require the following definition: Given integers w > 2 and k > 2, let m(w, k) denote the minimum order of a cyclically k-edge-connected snark with oddness at least w. For example, one has m(2, 2) = m(2, 3) = m(2,4) = m(2,5) = 10 as exemplified by the Petersen graph, and m(2, 6) = 28 as exemplified by the Isaacs flower snark J7. The values m(2, k) for k > 7 are not known, however the well-known conjecture of Jaeger and Swart [31] that there are no cyclically 7-edge-connected snarks would imply that these values are not defined. For w = 4, Lukot'ka et al. [35, Theorem 12] showed that m(4, 2) = m(4,3) = 28. The value m(4,4) remains unknown although our Theorem 1.1 seems to suggest that m(4,4) = 44.
Problem 5.1. Determine the value m(4,4).
Our second problem asks whether the function m(w, k) is monotonous in both coordinates.
Problem 5.2. Is it true that m(w +1, k) > m(w, k) and m(w, k + 1) > m(w, k) whenever the involved values are defined?
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 295
6 Testing conjectures
After having generated all snarks from the set S34 and those from S36 that have girth at least 5, Brinkmann et al. [7] tested the validity of several important conjectures whose minimal counterexamples, provided that they exist, must be snarks. For most of the considered conjectures the potential minimal counterexamples are proven to be nontrivial snarks, that is, those with cyclic connectivity at least 4 and girth at least 5. Nevertheless, in some cases the girth condition has not been established. Therefore it appears reasonable to check the validity of such conjectures on the set S36 \ S34 of all cyclically 4-edge-connected snarks of order 36. We have performed these tests and arrived at the conclusions discussed below; for more details on the conjectures we refer the reader to [7].
A dominating circuit in a graph G is a circuit C such that every edge of G has an end-vertex on C. Fleischner [17] made the following conjecture on dominating cycles.
Conjecture 6.1 (Dominating circuit conjecture). Every cyclically 4-edge-connected snark has a dominating circuit.
The dominating circuit conjecture exists in several different forms (see, for example, [3, 18]) and is equivalent to a number of other seemingly unrelated conjectures such as the Matthews-Sumner conjecture about the hamiltonicity of claw-free graphs [38]. For more information on these conjectures see [10].
Our tests have resulted in the following claim.
Claim 6.2. Conjecture 6.1 has no counterexample on 36 or fewer vertices.
The total chromatic number of a graph G is the minimum number of colours required to colour the vertices and the edges of G in such a way that adjacent vertices and edges have different colours and no vertex has the same colour as its incident edges. The total colouring conjecture [4, 50] suggests that the total chromatic number of every graph with maximum degree A is either A +1 or A + 2. For cubic graphs this conjecture is known to be true by a result of Rosenfeld [45], therefore the total chromatic number of a cubic graph is either 4 or 5. Cavicchioli et al. [12, Problem 5.1] asked for a smallest nontrivial snark with total chromatic number 5. Brinkmann et al. [7] showed that such a snark must have at least 38 vertices. Sasaki et al. [46] displayed examples of snarks with connectivity 2 or 3 whose total chromatic number is 5 and asked [46, Question 2] for the order of a smallest cyclically 4-edge-connected snark with total chromatic number 5. Brinkmann et al. [9] constructed cyclically 4-edge-connected snarks with girth 4 and total chromatic number 5 for each even order greater than or equal to 40. Our next claim shows that the value asked for by Sasaki et al. is either 38 or 40.
Claim 6.3. All cyclically 4-edge-connected snarks with at most 36 vertices have total chromatic number 4.
The following conjecture was made by Jaeger [30] and is known as the Petersen colouring conjecture. If true, this conjecture would imply several other profound conjectures, in particular, the 5-cycle double cover conjecture and the Fulkerson conjecture.
Conjecture 6.4 (Petersen colouring conjecture). Every bridgeless cubic graph G admits a colouring of its edges using the edges of the Petersen graph as colours in such a way that any three mutually adjacent edges of G are coloured with three mutually adjacent edges of the Petersen graph.
296
Ars Math. Contemp. 16 (2019) 277-298
It is easy to see that the smallest counterexample to this conjecture must be a cyclically
4-edge-connected snark. Brinkmann et al. [7] showed that the smallest counterexample to
the Petersen colouring conjecture must have order at least 36. Here we improve the latter
value to 38.
Claim 6.5. Conjecture 6.4 has no counterexamples on 36 or fewer vertices. References
[1]	G. M. Adelson-Velsky and V. K. Titov, On edge 4-chromatic cubic graphs (in Russian), in: V. K. Zakharov, V. P. Kozyrev, K. A. Rybnikov, V. N. Sachkov, V. E. Stepanov and V. E. Tarakanov (eds.), Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics (Moscow State University, Moscow, January 27-29, 1971), Moscow, 1973 pp. 5-14.
[2]	L. D. Andersen, H. Fleischner and B. Jackson, Removable edges in cyclically 4-edge-connected cubic graphs, Graphs Combin. 4 (1988), 1-21, doi:10.1007/bf01864149.
[3]	P. Ash and B. Jackson, Dominating cycles in bipartite graphs, in: J. A. Bondy and U. S. R. Murty (eds.), Progress in Graph Theory, Academic Press, Toronto, Ontario, 1984 pp. 81-87, proceedings of the conference on combinatorics held at the University of Waterloo, Waterloo, Ontario, 1982.
[4]	M. Behzad, G. Chartrand and J. K. Cooper, Jr., The colour numbers of complete graphs, J. London Math. Soc. 42 (1967), 226-228, doi:10.1112/jlms/s1-42.1.226.
[5]	D. Blanusa, Problem cetiriju boja, GlasnikMat. Fiz. Astr. Ser. II1 (1946), 31-42.
[6]	G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. Mflot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (2013), 311-314, doi:10.1016/j.dam.2012.07.018, available at http://hog.grinvin.org/.
[7]	G. Brinkmann, J. Goedgebeur, J. Hagglund and K. Markstrom, Generation and properties of snarks, J. Comb. Theory Ser. B 103 (2013), 468-488, doi:10.1016/j.jctb.2013.05.001.
[8]	G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discrete Math. Theor. Comput. Sci. 13 (2011), 69-80, https://www.dmtcs.org/dmtcs-ojs/ index.php/dmtcs/article/view/18 01/0.html.
[9]	G. Brinkmann, M. Preissmann and D. Sasaki, Snarks with total chromatic number 5, Discrete Math. Theor. Comput. Sci. 17 (2015), 369-382, https://www.dmtcs.org/ dmtcs-ojs/index.php/dmtcs/article/view/2 5 67.1.html.
[10]	H. Broersma, G. Fijavz, T. Kaiser, R. Kuzel, Z. Ryjdcek and P. Vrdna, Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks, Discrete Math. 308 (2008), 6064-6077, doi:10.1016/j.disc.2007.11.026.
[11]	P. J. Cameron, A. G. Chetwynd and J. J. Watkins, Decomposition of snarks, J. Graph Theory 11 (1987), 13-19, doi:10.1002/jgt.3190110104.
[12]	A. Cavicchioli, T. E. Murgolo, B. Ruini and F. Spaggiari, Special classes of snarks, Acta Appl. Math. 76 (2003), 57-88, doi:10.1023/a:1022864000162.
[13]	M. Chladn^ and M. Skoviera, Factorisation of snarks, Electron. J. Combin. 17 (2010), #R32, https://www.combinatorics.org/ojs/index.php/eljc/article/view/ v17i1r32.
[14]	B. Descartes, Network-colourings, Math. Gaz. 32 (1948), 67-69, doi:10.2307/3610702.
[15]	M. A. Fiol, A Boolean algebra approach to the construction of snarks, in: Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk (eds.), Graph Theory, Combinatorics, and Applications, Volume 1, John Wiley & Sons, New York, Wiley-Interscience Publication, 1991 pp.
J. Goedgebeur et al.: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 297
493-524, proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs held at Western Michigan University, Kalamazoo, Michigan, May 30 -June 3, 1988.
[16]	M. A. Fiol, G. Mazzuoccolo and E. Steffen, On measures of edge-uncolorability of cubic graphs: A brief survey and some new results, 2017, arXiv:1702.07156 [math.CO].
[17]	H. Fleischner, Cycle decompositions, 2-coverings, removable cycles, and the four-color disease, in: J. A. Bondy and U. S. R. Murty (eds.), Progress in Graph Theory, Academic Press, Toronto, Ontario, 1984 pp. 233-246, proceedings of the conference on combinatorics held at the University of Waterloo, Waterloo, Ontario, 1982.
[18]	H. Fleischner and M. Kochol, A note about the dominating circuit conjecture, Discrete Math. 259 (2002), 307-309, doi:10.1016/s0012-365x(02)00588-5.
[19]	M. Fontet, Graphes 4-essentiels, C. R. Acad. Sci. Paris Ser. A 287 (1978), 289-290.
[20]	J.-L. Fouquet, Graphes cubiques d'indice chromatique quatre, Ann. Discrete Math. 9 (1980), 23-28, doi:10.1016/s0167-5060(08)70028-1.
[21]	J. Goedgebeur, Source code of two programs to compute the oddness of a graph, http:// caagt.ugent.be/oddness/.
[22]	J. Goedgebeur, On the smallest snarks with oddness 4 and connectivity 2, Electron. J. Combin. 25 (2018), #P2.15, https://www.combinatorics.org/ojs/index.php/eljc/ article/view/v25i2p15.
[23]	J. Goedgebeur, E. Mâcajovâ and M. Skoviera, The smallest nontrivial snarks of oddness 4, in prepration.
[24]	R. Haggkvist and S. McGuinness, Double covers of cubic graphs with oddness 4, J. Comb. Theory Ser. B 93 (2005), 251-277, doi:10.1016/j.jctb.2004.11.003.
[25]	J. Hagglund, On snarks that are far from being 3-edge colorable, Electron. J. Combin. 23 (2016), #P2.6, https://www.combinatorics.org/ojs/index.php/eljc/ article/view/v2 3i2p6.
[26]	I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981), 718-720, doi: 10.1137/0210055.
[27]	A. Huck and M. Kochol, Five cycle double covers of some cubic graphs, J. Comb. Theory Ser. B 64 (1995), 119-125, doi:10.1006/jctb.1995.1029.
[28]	R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975), 221-239, doi:10.2307/2319844.
[29]	F. Jaeger, A survey of the cycle double cover conjecture, in: B. R. Alspach and C. D. Godsil (eds.), Cycles in Graphs, North-Holland, Amsterdam, volume 115 of North-Holland Mathematics Studies, 1985 pp. 1-12, doi:10.1016/s0304-0208(08)72993-1, papers from the workshop held at Simon Fraser University, Burnaby, British Columbia, July 5 - August 20, 1982.
[30]	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, California, pp. 71-95, 1988.
[31]	F. Jaeger and T. Swart, Problem session, Ann. Discrete Math. 9 (1980), 304-305, doi:10.1016/ s0167-5060(08)70086-4.
[32]	E. L. Johnson, A proof of 4-coloring the edges of a cubic graph, Amer. Math. Monthly 73 (1966), 52-55, doi:10.2307/2313923.
[33]	M. Kochol, Superposition and constructions of graphs without nowhere-zero k-flows, European J. Combin. 23 (2002), 281-306, doi:10.1006/eujc.2001.0563.
298
Ars Math. Contemp. 16(2019)299-317
[34]	R. Lukot'ka, E. Mdcajovd, J. Mazik and M. Skoviera, Erratum to "Small snarks with large oddness", in preparation.
[35]	R. Lukot'ka, E. Mdcajovd, J. Mazdk and M. Skoviera, Small snarks with large oddness, Electron. J. Combin. 22 (2015), #P1.51, https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v22i1p51.
[36]	E. Mdcajovd and M. Skoviera, Irreducible snarks of given order and cyclic connectivity, Discrete Math. 306 (2006), 779-791, doi:10.1016/j.disc.2006.02.003.
[37]	E. Mdcajovd and M. Skoviera, Sparsely intersecting perfect matchings in cubic graphs, Com-binatorica 34 (2014), 61-94, doi:10.1007/s00493-014-2550-4.
[38]	M. M. Matthews and D. P. Sumner, Hamiltonian results in K1>3-free graphs, J. Graph Theory 8 (1984), 139-146, doi:10.1002/jgt.3190080116.
[39]	B. D. McKay, nauty User's Guide (Version 1.5), Technical Report TR-CS-90-02, Department of Computer Science, Australian National University, 1990, the latest version of the software is available at http://cs.anu.edu.au/~bdm/nauty.
[40]	B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94-112, doi:10.1016/j.jsc.2013.09.003.
[41]	R. Nedela and M. Skoviera, Atoms of cyclic connectivity in cubic graphs, Math. Slovaca 45
(1995),	481-499.
[42]	R. Nedela and M. Skoviera, Decompositions and reductions of snarks, J. Graph Theory 22
(1996),	253-279, doi:10.1002/(sici)1097-0118(199607)22:3<253::aid-jgt6>3.0.co;2-l.
[43]	N. Robertson, Minimal cyclic-4-connected graphs, Trans. Amer. Math. Soc. 284 (1984), 665687, doi:10.2307/1999101.
[44]	R. W. Robinson and N. C. Wormald, Almost all cubic graphs are Hamiltonian, Random Structures Algorithms 3 (1992), 117-125, doi:10.1002/rsa.3240030202.
[45]	M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971), 396-402, doi: 10.1007/bf02771690.
[46]	D. Sasaki, S. Dantas, C. M. H. de Figueiredo and M. Preissmann, The hunting of a snark with total chromatic number 5, Discrete Appl. Math. 164 (2014), 470-481, doi:10.1016/j.dam.2013. 04.006.
[47]	C. E. Shannon, A theorem on coloring the lines of a network, J. Math. Physics 28 (1949), 148-151, doi:10.1002/sapm1949281148.
[48]	E. Steffen, Classification and characterizations of snarks, Discrete Math. 188 (1998), 183-203, doi:10.1016/s0012-365x(97)00255-0.
[49]	E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), 191-214, doi: 10.1016/j.disc.2003.05.005.
[50]	V. G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Diskret. Analiz 3 (1964), 25-30.
[51]	N. C. Wormald, Classifying k-connected cubic graphs, in: A. F. Horadam and W. D. Wallis (eds.), Combinatorial Mathematics VI, Springer, Berlin, volume 748 of Lecture Notes in Mathematics, pp. 199-206, 1979, doi:10.1007/bfb0102696, proceedings of the Sixth Australian Conference held at the University of New England, Armidale, August, 1978.