On cyclically 4-connected cubic graphs

Abstract

A 3-connected cubic graph is cyclically 4-connected if it has at least $n\ge 8$ vertices and when removal of a set of three edges results in a disconnected graph, only one component has cycles. By introducing the notion of cycle spread to quantify the distance between pairs of edges, we get a new characterization of cyclically 4-connected graphs. Let $Q_n$ and $V_n$ denote the ladder and Möbius ladder on $n\ge 8$ vertices, respectively. We prove that a 3-connected cubic graph G is cyclically 4-connected if and only if G is either the Petersen graph, $Q_n$ or $V_n$ for $n\ge 8$, or G is obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. The concept of cycle spread also naturally leads to methods for constructing cyclically k-connected cubic graphs from smaller ones, but for $k\ge 5$ the method is not exhaustive.

Keywords:

• Cubic graphs
• cyclically 4-connected graphs
• snarks

1 Introduction

A cubic graph is a graph whose vertices have degree 3. Let G be a simple cubic graph with n vertices and m edges. Then n is even and $m=\frac{3n}{2}$. In this paper we seek to understand the structure of and relationships between cyclically k-connected cubic graphs. There are several unresolved conjectures about cubic graphs such as Barnette’s conjecture that bipartite planar cubic graphs are Hamiltonian [1]. Cubic graphs model, for example, the molecular structure of sphere-shaped carbon molecules called fullerenes that form the basis for many patents for commercial applications [7]. Perhaps the most enduring problem involving cubic graphs is the hunt for bridgeless cubic graphs with edge chromatic number 4, called snarks, initiated by Tait when he proved that the Four-color Theorem is true if and only if snarks are non-planar [14]. A snark is non-trivial if it is cyclically 4-connected and has girth at least 5.

A k -connected graph is one with at least $k+1$ vertices that remains connected if fewer than k vertices are removed. The degree of every vertex in a cubic graph is 3, so it cannot have connectivity higher than 3. As a result, a concept called cyclic k-connectivity is used to define finer levels of connectivity. An edge-cut is a set of edges whose removal disconnects the graph. An edge-cut X is cycle-separating if at least two of the components in the disconnected graph formed when X is removed have cycles.

A 3-connected cubic graph is cyclically k-connected if it has at least $n\ge 2k$ vertices and it has no cycle-separating edge-cut of size less than k. Observe that, a cyclically 4-connected cubic graph will not have any cycles of length 3 since if it does, the 3 edges incident to the 3 vertices of the cycle may be removed to obtain two components with cycles [9]. A cycle with k vertices is called a k -cycle. A cycle with 3 vertices is called a triangle and a graph without triangles is called triangle-free. Therefore a cyclically 4-connected cubic graph is triangle-free, has $n\ge 8$ vertices, and when removal of a set of 3 edges results in a disconnected graph, only one component has cycles.

Figure 1 displays two well-known infinite families of cyclically 4-connected cubic graphs: the ladders $Q_{2k}$ and the Möbius ladders $V_{2k}$ for $k\ge 4$. Label the vertices $1,\dots ,k,k+1,\dots ,2k$ as shown. Edges with consecutively labeled end vertices such as $(1,2)$ are the “sides” of the ladder and edges that go across such as $(1,k+1)$ are the “rungs” of the ladder.

Figure 1: $Q_{2k}$, $k\ge 4$ (left), and $V_{2k}$, $k\ge 4$ (right).

The terminology follows [6] for the most part. Two distinct edges are adjacent if they have a common vertex, and non-adjacent otherwise. An edge joining two vertices in a cycle, but not along the cycle, is called a chord. It is well known that every pair of edges in a 2-connected graph is contained in at least one cycle.

Let G be a 2-connected graph and let ab and cd be a pair of edges. Let C be a smallest cycle containing ab and cd. There are two distinct paths in C connecting ab and cd. Without loss of generality, assume that the two paths connect a to c and b to d, respectively, and that the $a-c$ path is no longer than the $b-d$ path. Associate a pair $(i,j)$ where $i\le j$ with ab and cd that consists of the lengths of these two paths. If there are multiple smallest cycles resulting in different pairs $(i,j)$, take the one that is first in lexicographic order. We call this pair of numbers $(i,j)$ the cycle spread of edges ab and cd. Furthermore, we say that a pair of edges ab and cd have cycle spread at least $(i,j)$ if the cycle spread of ab and cd is greater than or equal to $(i,j)$ in lexicographic order.

Figure 2 displays examples of cycle spread. If ab and cd are adjacent, their cycle spread is $(0,j)$ for some $j\ge 1$. For example, the cycle spread of two edges in a triangle is $(0,1)$. Next, let ab and cd be non-adjacent edges. Then a smallest cycle containing them has size at least 4. If the size of a smallest cycle containing them is 4, then their cycle spread is $(1,1)$. If the size of a smallest cycle containing them is 5, then their cycle spread is $(1,2)$. If the size of a smallest cycle containing them is 6, then there are two possibilities for their cycle spread: $(1,3)$ or $(2,2)$. Both are shown in Figure 2. Furthermore, if the smallest cycles containing ab and cd include two 6-cycles with pairs of numbers $(1,3)$ and $(2,2)$ associated with them, then their cycle spread is $(1,3)$ because $(1,3)$ is less than $(2,2)$ in lexicographic order. To complete the definition, if edges ab and cd are the same, by convention their cycle spread is $(0,0)$. Thus, as noted earlier, if ab and cd are non-adjacent edges in a 4-cycle, then their cycle spread is $(1,1)$. Whereas, if ab and cd are non-adjacent edges that are not in any 4-cycle, their cycle spread is at least $(1,2)$.

Figure 2: Examples of cycle spread.

A bridge addition of a graph G is obtained from G by selecting a pair of distinct edges ab and cd, subdividing them by vertices x and y, respectively, forming paths of length 2, and joining x and y by an edge (see Figure 3). We call this the bridging operation. The new graph $G^{\prime }$ is called a bridge addition of G. It has two new vertices x and y and edges xa, xb, yc, yd, and xy. Observe that, $G^{\prime }$ has three more edges than G. Reversing the bridging operation is called unbridging.

Figure 3: Bridging two edges.

For example, as illustrated in Figure 4, $K_4$ has two non-isomorphic bridge additions, the prism graph and $K_{3,3}$. The four bridge additions of the prism graph and $K_{3,3}$ are also shown. Of these only $Q_8$ and $V_8$ are cyclically 4-connected. Observe that, bridging a pair of edges in a 3-connected cubic graph results in a graph that remains 3-connected and cubic. Figure 5 displays the cyclically 4-connected cubic graphs arising from $Q_8$ and $V_8$ via bridge additions. Note that, $P_{10}$ is the Petersen graph. Observe that, bridging a pair of non-adjacent edges in a cyclically 4-connected cubic graph results in a graph that remains cyclically 4-connected and cubic. The next theorem is the main result of this paper.

Figure 4: All 3-connected cubic graphs with 6, 7, and 8 vertices.

Figure 5: All cyclically 4-connected cubic graphs with 8 and 10 vertices.

Theorem 1.1.

Let G be a 3-connected cubic graph on $n\ge 8$ vertices. Then G is cyclically 4-connected if and only if

1. $G\cong P_{10}$, $V_n$, or $Q_n$ for some $n\ge 8$ ; or

2. G is obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$.

One direction of the proof is straightforward. The Petersen graph and the infinite families of ladders and Möbius ladders are cyclically 4-connected cubic graphs, and bridging non-adjacent edges of a cyclically 4-connected cubic graph results in a graph that is also cyclically 4-connected and cubic. The other direction requires a proof. Section 2 has preliminaries. Section 3 has a key lemma used in the proof of Theorem 1.1. Section 4 has the proof of Theorem 1.1.

2 Background

The bridging operation first appeared in 1967 in books by Grünbaum [4] and Tutte [15] in the context of 3-connected cubic graphs. Grünbaum proved that every 3-connected cubic graph can be constructed from $K_4$ by repeatedly bridging edges [4]. Let G and H be 3-connected cubic graphs such that H is a minor of G and $G\cancel{\cong }{K}_4$. Tutte proved that G can be obtained from H by repeatedly bridging edges [15].

The next result states that every cyclically 4-connected cubic graph except $Q_8$ and $V_8$ can be obtained from a cyclically 4-connected cubic graph with fewer vertices by bridging non-adjacent edges. This result appears to have been discovered multiple times. See Fouquet and Thuiller [3] for the early history, where they note that the result was published by Titov and Adelson-Velski in 1973, by Fontet in 1978 [2], and by Wormald in 1979 [16]. They called the bridging and unbridging operations “$ϵ$-extension” and “$ϵ$-reduction”. Wormald referred to cyclically 4-connected graphs as “irreducible graphs”. He proved the following result: Each irreducible cubic graph other than $K_4$ and $Q_8$ can be obtained from an irreducible graph with fewer points by joining two non-adjacent lines ([16], Theorem 4).

In [8] Mahary calls bridge additions “handle extensions” and cites Fontet’s 1979 thesis, private communication with Robertson, Kelmans [5], and Wormald [16]. According to Mahary, a graph H is topologically contained in a graph G if a subdivision of H is isomorphic to a subgraph of G. He calls the result the “Cubic Cyclically-4-Connected Handle Theorem” and presents it as follows: The class of all cubic cyclically 4-connected graphs can be generated by repeatedly adding handles starting from $V_6$ and $Q_8$ ([8], Theorem 3.3).

The definition of cyclically 4-connected graphs has also evolved. Earlier authors did not specify that cyclically 4-connected graphs must have $n\ge 8$ vertices. They considered $V_6\cong K_{3,3}$ to be cyclically 4-connected. Our definition of cyclically 4-connected is from Robertson, Seymour, and Thomas [11]. In particular, we do not consider $K_{3,3}$ to be cyclically 4-connected and we start the process from 8 vertices. This presents no difficulty since $V_8$ is the only cyclically 4-connected cubic bridge addition of $K_{3,3}$.

Theorem 2.1.

Let G be a cyclically 4-connected cubic graph such that $G\cancel{\cong }{Q}_8,V_8$. Then G is obtained from a cyclically 4-connected cubic graph with fewer vertices by bridging pairs of non-adjacent edges. Moreover, each graph obtained in this manner is a cyclically 4-connected cubic graph.

As a corollary, Mahary shows that all cubic cyclically 4-connected graphs that do not topologically contain $Q_8$ can be obtained by repeated operations of adding a handle starting from $V_6$. Consequently, he proves the following result ([8], Theorem 3.5) noting that Kelmans also proved it independently in [5]: Let G be a cyclically 4-connected cubic graph that does not topologically contain $Q_8$. Then G is isomorphic to $P_{10}$ or $V_{2k}$ for $k\ge 4$.

In [16], at the end of his paper, Wormald briefly mentions that the distance between two edges e and f in a connected graph is one less than the length of the shortest path which includes e and f. We made precise the concept of distance between edges by introducing cycle spread. By this definition, two adjacent edges have distance 1, corresponding to cycle spread $(0,j)$ for some $j\ge 1$, and two non-adjacent edges have distance at least 2, corresponding to cycle spread at least $(1,1)$. After reviewing all the manifestations of Theorem 2.1, we found that it could be strengthened.

3 Triangle-free 2-connected cubic graphs

In this section we will prove that for a triangle-free 2-connected graph, under certain conditions, a bridge added to a pair of edges with cycle spread $(1,1)$ can be exchanged for a bridge added to a pair of edges with cycle spread at least $(1,2)$. The key insight in the proof is that a bridge added to a 4-cycle can “hop” to an adjacent 4-cycle, and that this process terminates either by returning to the original cycle in the case of $Q_{2k}$ and $V_{2k}$, or by reaching a pair of edges with cycle spread at least $(1,2)$.

Lemma 3.1

(Exchange Lemma).

Let H be a triangle-free 2-connected cubic graph with $n\ge 8$ vertices, and let G be obtained from H by bridging a pair of edges with cycle spread at least $(1,1)$. Then one of the following statements is true:

1. $H\cong Q_{2k}$ and $G\cong Q_{2(k+1)}$ for some $k\ge 4$ ;

2. $H\cong V_{2k}$ and $G\cong V_{2(k+1)}$ for some $k\ge 4$ ; or

3. G is obtained from H by bridging a pair of edges with cycle spread at least $(1,2)$.

Proof.

Since H is a triangle-free 2-connected cubic graph, and since G is obtained from H by bridging a pair of edges with cycle spread at least $(1,1)$, G will also be a triangle-free 2-connected cubic graph. Let ab and cd denote the pair of edges with cycle spread at least $(1,1)$ in H that can be bridged to obtain G.

Since H is 2-connected, ab and cd are in a cycle. However, since H has no triangles, ab and cd are not part of any triangle. If ab and cd have cycle spread at least $(1,2)$, there is nothing to prove. Therefore suppose that ab and cd have cycle spread exactly $(1,1)$. Then ab and cd form a 4-cycle with two other edges; without loss of generality say that ac and bd are also edges. Thus we have the 4-cycle acdba as shown in Figure 6. Since H is cubic, b and d are each incident with exactly one other edge outside the 4-cycle. Denote these edges by be and df as shown in Figure 6. Note that edges be and df are not adjacent, since H is triangle-free. Moreover, b and d are incident to no other edges since each vertex has degree 3.

Figure 6: A pair of edges in H with cycle spread $(1,1)$ with edges be and df incident to b and d.

As noted earlier, G is constructed from H by bridging edges ab and cd, as shown in the first diagram in Figure 7. Relabel the vertices of H as $a^{\prime }$, $b^{\prime }$, $c^{\prime }$, $d^{\prime }$, $e^{\prime }$, and $f^{\prime }$ and construct another graph $G^{\prime }$ by bridging edges $b^{\prime }{e}^{\prime }$ and $d^{\prime }{f}^{\prime }$, as shown in the second diagram in Figure 7. Now the only difference between G and $G^{\prime }$ is that G has a bridge xy of ab and cd, and $G^{\prime }$ has a bridge $x^{\prime }{y}^{\prime }$ of $b^{\prime }{e}^{\prime }$ and $d^{\prime }{f}^{\prime }$.

Figure 7: Exchanging one pair of bridged edges for another.

Define a function $\varphi :V(G)\to V(G^{\prime })$ as follows: $\varphi (b)=x^{\prime }$, $\varphi (d)=y^{\prime }$, $\varphi (x)=b^{\prime }$, $\varphi (y)=d^{\prime }$, and for all other corresponding pairs $(v,v^{\prime })\in V(G)\times V(G^{\prime })$, $\varphi (v)=v^{\prime }$. Clearly for any $$\begin{array}{c}v,w\in V(G)-\{a,b,c,d,e,f,x,y\}\hfill \end{array}$$

with corresponding $$\begin{array}{c}{v}^{\prime },w^{\prime }\in V(G^{\prime })-\{a^{\prime },b^{\prime },c^{\prime },d^{\prime },e^{\prime },f^{\prime },x^{\prime },y^{\prime }\},\hfill \end{array}$$

$\mathit{\text{vw}}\in E(G)$ if and only if $\varphi (v)\varphi (w)=v^{\prime }{w}^{\prime }\in E(G^{\prime })$. Observe that, $\varphi$ restricted to the subgraph of G induced by $\{a,b,c,d,e,f,x,y\}$ is an isomorphism with image the subgraph of $G^{\prime }$ induced by $\{a^{\prime },b^{\prime },c^{\prime },d^{\prime },e^{\prime },f^{\prime },x^{\prime },y^{\prime }\}$. Since H is cubic, among the vertices $a,b,c,d,e,f,x,y\in V(G)$, only a, c, e, and f are adjacent to any vertex other than a, b, c, d, e, f, x, y. Moreover, since each of these vertices is mapped by $\varphi$ to its corresponding vertex in $G^{\prime }$, $\varphi$ preserves all edges incident to these vertices, and therefore is an isomorphism between G and $G^{\prime }$.

If vertices e and f are not adjacent, then edges be and df have cycle spread at least $(1,2)$, and the result follows. Therefore suppose vertices e and f are adjacent. Then the cycle spread of edges be and df is $(1,1)$. In this case, vertices e and f are each incident to exactly one other edge, forming the 4-cycle bdfeb, as shown in Figure 8. These two edges incident to e and f, respectively, are not adjacent since H has no triangles. This process can be repeated, and the labeled edge xy may be viewed as “hopping” along the 4-cycles. Call each hop a 4 -cycle exchange and call the pattern of 4-cycles encountered during repeated 4-cycle exchanges a 4 -cycle chain. See the right-hand diagram in Figure 8.

Figure 8: Exchanging a bridge of one edge pair with cycle spread $(1,1)$ for another (left) and a 4-cycle chain (right).

Let J be a maximal 4-cycle chain in H and let k be the number of 4-cycles it contains. With at most $k 4$-cycle exchanges we must either reach a pair of edges not contained in a 4-cycle, which has cycle spread at least $(1,2)$, or reach a 4-cycle that has already been encountered. The only way to reach a 4-cycle that has already been encountered is if $J\cong Q_{2k}$ or $J\cong V_{2k}$, as shown in Figure 9. However, since H is connected it may not have any components distinct from the one containing J, and because H is cubic it may have no other edges. Therefore J is H itself. In conclusion, as illustrated by the first and last graphs in each row of Figure 9, only in these two graphs, we may begin with a bridge of a 4-cycle and through a sequence of 4-cycle exchanges, return to the same graph. ▪

Figure 9: Exchanging bridges of pairs of edges with cycle spread $(1,1)$ in $Q_{2k}$ and $V_{2k}$ to reach the same graph.

Note that H is only required to be a triangle-free 2-connected graph. If G is obtained from H by bridging a 4-cycle, then we can traverse a ladder of 4-cycles until we either reach a pair of edges with cycle spread at least $(1,2)$, or reach the 4-cycle where we started, in which case H must be $Q_{2k}$ or $V_{2k}$ as indicated in Figure 7. Observe that, in Figures 6 and 7, the subgraph shown is connected to the remainder of G only via the additional edges incident with vertices a, c, e, and f, because the graph is cubic. This is what allows us to exchange a bridge of ab and cd with a bridge of be and df and get isomorphic graphs.

We can illustrate the exchange that occurs in Lemma 3.1 by examining bridges of pairs of edges with cycle spread exactly $(1,1)$ in $Q_{10}$. There are two ways such a bridge can occur:

• By adding a rung to the graph; or

• By bridging a pair of two rungs that appear together in a 4-cycle.

Both ways are illustrated in Figure 10. In the first case, shown on the left, $Q_{12}$ is produced from $Q_{10}$. In the second case, shown on the right, the bridge can be exchanged for a bridge of two edges with cycle spread $(1,2)$.

Figure 10: Planar graphs obtained by bridging edges in $Q_{10}$.

The result is not true if the graph contains triangles, as in the graph on the left in Figure 11, because the edges incident to two vertices in a 4-cycle may be adjacent. The result is also not true if the graph is not cubic as in the graph on the right in Figure 11, because then the vertices in the 4-cycle may be incident to other edges. In this case the graph produced by the exchange is not isomorphic to the graph with the original bridge.

Figure 11: Counterexamples to Lemma 3.1 if G contains triangles (left) or is not cubic (right).

Finally, the result is not true if the graph is not 2-connected since there may be pairs of edges that do not lie in any cycle.

4 Proof of Theorem 1.1

In this section we will prove Theorem 1.1, which states that G is a cubic cyclically 4-connected graph if and only if G is the Petersen graph or a member of the infinite families of ladders or Möbius ladders, or G is obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$.

Proof of Theorem 1.1.

The proof is by induction on $n\ge 8$. From Figure 5, observe that, $Q_8$ and $V_8$ are the only cyclically 4-connected cubic graphs on 8 vertices. The non-isomorphic cyclically 4-connected cubic graphs obtained from $Q_8$ and $V_8$ by bridging pairs of edges with cycle spread $(1,1)$ are $Q_{10}$ and $V_{10}$, respectively. The other 10-vertex graphs $A_{10}$, $B_{10}$, and $P_{10}$ are non-planar and can be obtained from $V_8$ by bridging a pair of edges with cycle spread at least $(1,2)$ as illustrated in Figure 5. It is easily checked that $A_{10}$ and $B_{10}$ can also be obtained from $Q_8$ by bridging pairs of edges with cycle spread at least $(1,2)$.

To show that the result holds for $n=12$, we only need to examine the cyclically 4-connected bridge additions of $Q_{10}$, $V_{10}$, and $P_{10}$. Figure 12 shows the seven non-isomorphic cyclically 4-connected bridge additions of $V_{10}$. Observe that, $V_{12}$ is the only one that requires bridging a 4-cycle; the other six can be obtained from $A_{10}$ or $B_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. Figure 13 shows the two non-isomorphic cyclically 4-connected bridge additions of $P_{10}$. Both are also obtained from $A_{10}$ and $B_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. Thus, the result holds for $n=8,10,12$.

Figure 12: The non-isomorphic cyclically 4-connected bridge additions of $V_{10}$.

Figure 13: The non-isomorphic cyclically 4-connected bridge additions of $P_{10}$.

Suppose $n\ge 14$ and let G be a cyclically 4-connected cubic graph with n vertices. By Theorem 2.1, G can be obtained from a cyclically 4-connected cubic graph H with $n-2$ vertices by bridging a pair of non-adjacent edges, that is a pair of edges with cycle spread at least $(1,1)$. Since H is cubic and cyclically 4-connected, it is triangle-free. By Lemma 3.1, one of the following statements is true:

1. $H\cong Q_{n-2}$ and $G\cong Q_n$;

2. $H\cong V_{n-2}$ and $G\cong V_n$; or

3. G can be obtained from H by bridging a pair of edges with cycle spread at least $(1,2)$.

If (i) or (ii) is true, the result follows. Therefore, suppose (i) and (ii) do not hold, and suppose G can be obtained from H, which has $n-2$ vertices, by bridging a pair of edges with cycle spread at least $(1,2)$. By the induction hypothesis, $H\cong V_{n-2}$, $H\cong Q_{n-2}$, or H can be obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. We will consider these cases separately.

Case (i) Suppose $H\cong V_{n-2}$. Let ab and cd be the pair of non-adjacent edges bridged in $V_{n-2}$ to obtain G. Then there must be a rung xy in $V_{n-2}$ not equal to or adjacent to ab or cd that can be unbridged to obtain $V_{n-4}$ which still contains edges ab and cd, which remain non-adjacent. We can bridge ab and cd in $V_{n-4}$ to get a cyclically 4-connected graph $H^{\prime }$, and then return xy to get G. Since $G\ncong V_n$, by Lemma 3.1, G can also be obtained from $H^{\prime }$ by bridging a pair of edges with cycle spread at least $(1,2)$. Observe that, $H^{\prime }\ncong V_{n-2}$ because otherwise $G\cong V_n$, which violates the assumption made at the beginning of the previous paragraph. Moreover, $H^{\prime }\ncong Q_{n-2}$ because $Q_{n-2}$ cannot be obtained from $V_{n-4}$ by bridging a pair of edges. Therefore by the induction hypothesis, $H^{\prime }$ can be obtained from $Q_8$ or $Q_{10}$, by bridging pairs of edges with cycle spread at least $(1,2)$, and consequently so can G.

Case (ii) Suppose $H\cong Q_{n-2}$. As in the previous case, let ab and cd be the pair of non-adjacent edges bridged in $Q_{n-2}$ to obtain G. Then there must be a rung xy in $Q_{n-2}$ not equal to or adjacent to ab or cd that can be unbridged to obtain $Q_{n-4}$ which still contains edges ab and cd, which remain non-adjacent. We can bridge ab and cd in $Q_{n-4}$ to get a cyclically 4-connected graph $H^{\prime }$, and then return xy to get G. Since $G\ncong Q_n$, by Lemma 3.1, G can also be obtained from $H^{\prime }$ by bridging a pair of edges with cycle spread at least $(1,2)$. Since $H^{\prime }\ncong Q_{n-2}$ and $H^{\prime }\ncong V_{n-2}$, by the induction hypothesis, $H^{\prime }$ can be obtained from $Q_8$ or $Q_{10}$, by bridging pairs of edges with cycle spread at least $(1,2)$, and consequently so can G.

Case (iii) Suppose H can be obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. Then since G can be obtained from H by bridging a pair of edges with cycle spread at least $(1,2)$, we may conclude that G can be obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$.

In all three cases, G can be obtained from $Q_8$ or $Q_{10}$ by bridging pairs of edges with cycle spread at least $(1,2)$. □

The next step in this project is to generate cyclically 5-connected cubic graphs from smaller ones using results in [11] and [13]; a much more difficult task. In 1966 Tutte conjectured that every snark has a Peterson minor. Since then considerable progress has been made on this conjecture, see for example [10] and [12]. In [12] the authors prove that Tutte’s conjecture holds for girth six cyclically 5-connected cubic graphs. Another direction for this project is to generate non-planar cyclically 5-connected cubic graphs from smaller ones starting with the Petersen graph and graphs called the triplex, box, and ruby in [11] with the goal of finding snarks. Finally, in future work we will extend the results in this paper to the much larger class of cyclically 4-connected minimally 3-connected graphs.

Acknowledgments

The authors thank the referees for their useful suggestions.