Constructing Minimally 3-Connected Graphs

Abstract

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of G′ G′ from the cycles of G, where G′ G′ is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with n−1 n−1 vertices and m−2 m−2 edges, n−1 n−1 vertices and m−3 m−3 edges, and n−2 n−2 vertices and m−3 m−3 edges.

1. Introduction

In this paper, we present an algorithm for consecutively generating minimally 3-connected graphs, beginning with the prism graph, with the exception of two families. The two exceptional families are the wheel graph with n vertices andn−1spokes denoted by_Wn−1forn≥4and the complete bipartite graph with 3 vertices in one class andn−3vertices in the other class denoted by_K3,n−3forn≥6 . See Figure 1.

Tutte proved that a simple graph is 3-connected if and only if it is a wheel or is obtained from a wheel by adding edges between non-adjacent vertices and splitting vertices [1]. The vertex split operation is illustrated in Figure 2. At each stage the graph obtained is 3-connected.

A cubic graph is a graph whose vertices have degree 3. Let G and H be 3-connected cubic graphs such thatG≇_W3 and H is a minor of G. A pair of distinct edges is bridged if they are subdivided by vertices x and y, respectively, forming paths of length 2, and x and y are joined by an edge. This operation is explained in detail in Section 2 and illustrated in Figure 3. Tutte also proved that G can be obtained from H by repeatedly bridging edges. At each stage the graph obtained remains 3-connected and cubic [2]. Observe that this operation is equivalent to adding an edgee=uvto a cubic graph and splitting u and splitting v. This gives an easy way of consecutively constructing all 3-connected cubic graphs on n vertices for even n. Surprisingly the entry for the number of 3-connected cubic graphs in the Online Encyclopedia of Integer Sequences (sequence A204198) has entries only up ton=14. We were able to quickly obtain such graphs up ton=20.

Tutte’s result and our algorithm based on it suggested that a similar result and algorithm may be obtainable for the much larger class of minimally 3-connected graphs.

Dawes gave a necessary and sufficient characterization for the construction of minimally 3-connected graphs starting with_W3. To do this he needed three operations one of which is the above operation where two distinct edges are bridged. Lete=abbe an edge andx≠a,bbe a vertex. A vertex and an edge are bridged if a new vertex is placed on edge e and linked to x. Dawes proved that starting with_W3 the class of minimally 3-connected graphs can be constructed by bridging a vertex and an edge, bridging two edges, or by adding a degree 3 vertex in the manner Dawes specified using what he called “3-compatible sets” as explained in Section 2. Following the above approach for cubic graphs we were able to translate Dawes’ operations to edge additions and vertex splits and develop an algorithm that consecutively constructs minimally 3-connected graphs from smaller minimally 3-connected graphs.

First, we prove exactly how Dawes’ operations can be translated to edge additions and vertex splits. Second, we prove a cycle propagation result. Although obtaining the set of cycles of a graph is NP-complete in general, we can take advantage of the fact that we are beginning with a fixed cubic initial graph, the prism graph. We develop methods for constructing the set of cycles for a graph^G′obtained from a graph G by edge additions and vertex splits, and Dawes specifications on 3-compatible sets. Let n be the number of vertices in G and let c be the number of cycles of G. We prove that the set of cycles of^G′can be obtained from the set of cycles of G by a method with complexity O(^c2n). Third, we prove that if G is a minimally 3-connected graph that is not_Wn−1forn≥4or_K3,n−3forn≥6, then G must have a prism minor, forn≥7, and G can be obtained from a smaller minimally 3-connected graph^G′such that|E(G)|−|E(^G′)|≤3using edge additions and vertex splits and Dawes specifications on 3-compatible sets.

We present an algorithm based on the above results that consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs withn−1vertices andm−2edges,n−1vertices andm−3edges, and n−2vertices andm−3edges. This formulation also allows us to determine worst-case complexity for processing a single graph; namelyO(^{c2 n3}), which includes the complexity of cycle propagation mentioned above.

There has been a significant amount of work done on identifying efficient algorithms for certifying 3-connectivity of graphs. Hopcroft and Tarjan published a linear-time algorithm for testing 3-connectivity [3]. Schmidt extended this result by identifying a certifying algorithm for checking 3-connectivity in linear time [4]. The perspective of this paper is somewhat different. Instead of checking an existing graph to determine whether it is minimally 3-connected, we seek to construct graphs from the prism using a procedure that generates only minimally 3-connected graphs. The algorithm presented in this paper is the first to generate exclusively minimally 3-connected graphs from smaller minimally 3-connected graphs.

2. Terminology, Previous Results, and Outline of the Paper

We begin with the terminology used in the rest of the paper. Since graphs used in the paper are not necessarily simple, when they are it will be specified. Let G be a graph ande=uvbe an edge with end vertices u and v. The graph with edge e deleted is called an edge-deletion and is denoted byG\eorG\uv. When deleting edge e, the end vertices u and v remain. To contract edge e, collapse the edge by identifing the end vertices u and v as one vertex, and delete the resulting loop. The graph with edge e contracted is called an edge-contraction and denoted byG/e. A graph H is a minor of a graph G if H can be obtained from G by deleting edges (and any isolated vertices formed as a result) and contracting edges. We writeH=G\X/Y, where X is the set of edges deleted and Y is the set of edges contracted.

A triangle is a set of three edges in a cycle and a triad is a set of three edges incident to a degree 3 vertex. A graph is 3-connected if at least 3 vertices must be removed to disconnect the graph. In a 3-connected graph G, an edge e is deletable ifG\eremains 3-connected. A 3-connected graph with no deletable edges is called minimally 3-connected.

There are multiple ways that deleting an edge in a minimally 3-connected graph G can destroy connectivity. One obvious way is when G has a degree 3 vertex v and deleting one of the edges incident to v results in a 2-connected graph that is not 3-connected. Halin proved that a minimally 3-connected graph has at least one triad [5]. We exploit this property to develop a construction theorem for minimally 3-connected graphs.

The operation that reverses edge-deletion is edge addition. A simple graph G with an edgee=uvadded between non-adjacent vertices is called an edge addition of G and denoted byG+eorG+uv.

The operation that reverses edge-contraction is called a vertex split of G. To split a vertex v withde_gG(v)≥4, first divide_NG(v)into two disjoint sets S and T, both of size at least 2. Then replace v with two distinct vertices v and^v′, join them by a new edgef=v^v′, and join each neighbor of v in S to v and each neighbor in T to^v′. The resulting graph is called a vertex split of G and is denoted byK=G_∘S,Tf. In other words_NG(v)is partitioned into two sets S and T, and in K,_NK(v)=S∪^v′and_NK(^v′)=T∪v. Observe thatde_gK(v)≥3andde_gK(^v′)≥3.

We can get a different graph depending on the assignment of neighbors of v in G to v and^v′in the vertex split; hence the sets S and T in the notation. With a slight abuse of notation, we can sayG∘f, as each vertex split is described with a particular assignment of neighbors of v in G to v and^v′. When performing a vertex split, we will think of^v′as the new vertex that gets added andf=v^v′as the new edge that gets added. Observe that if G is 3-connected, then edge additions and vertex splits remain 3-connected. The degree conditionde_gG(v)≥4 is not necessary for an arbitrary vertex split, but required to preserve 3-connectivity. Figure 2 shows the vertex split operation.

In 1961 Tutte proved that a simple graph is 3-connected if and only if it is a wheel or is obtained from a wheel by a finite sequence of edge additions or vertex splits. This result is known as Tutte’s Wheels Theorem [1].

Theorem 1 (Tutte, 1961).Let G be a simple graph that is not a wheel. Then G is 3-connected if and only if G can be constructed from a wheel minor by a finite sequence of edge additions or vertex splits.

The next result we need is Dirac’s characterization of 3-connected graphs without a prism minor [6]. The graphs_K3,n−3′,_K3,n−3″, and_K3,n−3‴are obtained from the complete bipartite graph_K3,n−3 (shown in Figure 1) with one, two, or three edges, respectively, joining the three vertices in one class.

Theorem 2 (Dirac, 1963).

A simple 3-connected graph G has no prism-minor if and only if G is isomorphic to_K5\e,_K5,_Wn−1, forn≥4,_K3,n−3,_K3,n−3′,_K3,n−3″, or_K3,n−3‴, forn≥6.

Theorem 2 implies that there are only two infinite families of minimally 3-connected graphs without a prism-minor, namely_Wn−1forn≥4and_K3,n−3forn≥6. Thus, we may focus on constructing minimally 3-connected graphs with a prism minor.

Next, Halin proved that minimally 3-connected graphs are sparse in the sense that there is a linear bound on the number of edges in terms of the number of vertices [5].

Theorem 3 (Halin, 1969).

Let G be a minimally 3-connected graph onn≥8vertices. Then|E(G)|≤3n−9. Moreover,|E(G)|=3n−9if and only ifG≅_K3,n−3.

In 1969 Barnette and Grünbaum defined two operations based on subdivisions and gave an alternative construction theorem for 3-connected graphs [7]. A subdivision of G is obtained from G by replacing an edge by a path of length at least 2. Let G be a 3-connected graph. The first Barnette and Grünbaum operation is defined as follows: Subdivide an edgeabby vertex y and add edgexyfor a vertexx≠a,b . This is what we called “bridging a vertex and an edge” in Section 1. The second Barnette and Grünbaum operation is defined as follows: Subdivide two distinct edgesabandcd, by vertices x and y, respectively, and add edgexy . This is what we called “bridging two edges” in Section 1. Observe that these operations, illustrated in Figure 3, preserve 3-connectivity.

Theorem 4 (Barnette and Grünbaum, 1968).

Let G be a simple graph such thatG≇_W3. Then G is 3-connected if and only if G can be constructed from_W3by a finite sequence of edge additions, bridging a vertex and an edge, or bridging two edges.

In 1986, Dawes gave a necessary and sufficient characterization for the construction of minimally 3-connected graphs starting with_W3 . He used the two Barnett and Grünbaum operations (bridging an edge and bridging a vertex and an edge) and a new operation, shown in Figure 4, that he defined as follows: select three distinct verticesx,y,zin the graph and link all three to a new vertex w by adding three new edgesxw,yw, andzw. Observe that this new operation also preserves 3-connectivity. We will call this operation “adding a degree 3 vertex” or in matroid language “adding a triad” since a triad is a set of three edges incident to a degree 3 vertex. Using these three operations, Dawes gave a necessary and sufficient condition for the construction of minimally 3-connected graphs.

Dawes thought of the three operations, bridging edges, bridging a vertex and an edge, and the third operation as acting on, respectively, a vertex and an edge, two edges, and three vertices. Dawes showed that if one begins with a minimally 3-connected graph and applies one of these operations, the resulting graph will also be minimally 3-connected if and only if certain conditions are met. Let C be a cycle in a graph G. A chord of C is an edgee∉C that links two vertices in C. A chording path P for a cycle C is a path that has a chord e of C in it and intersects C only in the end vertices of e. In particular, none of the edges of C can be in the path. See Figure 5.

When applying the three operations listed above, Dawes defined conditions on the set of vertices and/or edges being acted upon that guarantee that the resulting graph will be minimally 3-connected. A set S of vertices and/or edges in a graph G is 3-compatible if it conforms to one of the following three types:

• S={x,ab}, where x is a vertex of G,abis an edge of G,x≠a,band noxa-path orxb-path is a chording path ofG−ab;

• S={ab,cd}, whereabandcdare distinct edges of G, though possibly adjacent, and noac-,bc-,ad- orbd-path is a chording path ofG−{ab,cd}; or

• S={x,y,z}, where x, y, and z are distinct vertices of G and noxy-,xz- oryz-path is a chording path of G. Please note that if G is 3-connected, then x, y, and z must be pairwise non-adjacent if{x,y,z}is 3-compatible.

For convenience in the descriptions to follow, we will use D1, D2, and D3 to refer to bridging a vertex and an edge, bridging two edges, and adding a degree 3 vertex, respectively. Dawes proved that if one of the operations D1, D2, or D3 is applied to a minimally 3-connected graph, then the result is minimally 3-connected if and only if the operation is applied to a 3-compatible set [8].

Theorem 5 (Dawes, 1986a).Let H be a minimally 3-connected graph. Let G be constructed from H by applying D1, D2, or D3 to a set S of edges and/or vertices of H. Then G is minimally 3-connected if and only if S is a 3-compatible set in H.

Dawes also proved that, with the exception of_W3, every minimally 3-connected graph can be obtained by applying D1, D2, or D3 to a 3-compatible set in a smaller minimally 3-connected graph.

Theorem 6 (Dawes, 1986b).

Let G be a simple graph such thatG≇_W3. Then G is minimally 3-connected if and only if there exists a minimally 3-connected graph^G′,|E(^G′)|<|E(G)|such that G can be constructed by applying one of D1, D2, or D3 to a 3-compatible set in^G′.

The next result is the Strong Splitter Theorem [9]. The rank of a graph, denoted byr(G), is the size of a spanning tree. If G has n vertices, thenr(G)=n−1.

Theorem 7.

Suppose G and H are simple 3-connected graphs such that G has a proper H-minor, G is not a wheel, andH≇_W3. Letj=r(G)−r(H). Then there is a sequence of 3-connected graphs_G0,_G1,…,_Gtsuch that_G0≅H,_Gt=G, and_Gi−1is a minor of_Gisuch that:

(i)

For1≤i≤j,r(_Gi)−r(_Gi−1)=1and|E(_Gi)|−|E(_Gi−1)|≤3; and

(ii)

Forj<i≤t,r(_Gi)=r(G)and|E(_Gi)|−|E(_Gi−1)|=1.

Moreover, when|E(_Gi)|−|E(_Gi−1)|=3, for1≤i≤j,E(_Gi)−E(_Gi−1)is a triad of_Gi.

Our goal is to generate all minimally 3-connected graphs with n vertices and m edges, for various values of n and m by repeatedly applying operations D1, D2, and D3 to input graphs after checking the input sets for 3-compatibility. The process needs to be correct, in that it only generates minimally 3-connected graphs, exhaustive, in that it generates all minimally 3-connected graphs, and isomorph-free, in that no two graphs generated by the algorithm should be isomorphic to each other.

By Theorem 5, in order for our method to be correct it needs to verify that a set of edges and/or vertices is 3-compatible before applying operation D1, D2, or D3. In Section 3, we present two of the three new theorems in this paper. The first new result expresses operations D1, D2, and D3 in terms of edge additions and vertex splits. The second new result gives an algorithm for the efficient propagation of the list of cycles of a graph from a smaller graph when performing edge additions and vertex splits. We call it the “Cycle Propagation Algorithm.” Together, these two results establish correctness of the method. In Section 4 we provide details of the implementation of the Cycle Propagation Algorithm.

In Section 5 we present the algorithm for generating minimally 3-connected graphs using an “infinite bookshelf” approach to the removal of isomorphic duplicates by lists. Specifically, we show how we can efficiently remove isomorphic graphs from the list of generated graphs by restructuring the operations into atomic steps and computing only graphs with fixed edge and vertex counts in batches.

In Section 6 we show that the “Infinite Bookshelf Algorithm” described in Section 5 is exhaustive by showing that all minimally 3-connected graphs with the exception of two infinite families,_Wn−1and_K3,n−3, can be obtained from the prism graph by applying operations D1, D2, and D3. This is the third new theorem in the paper.

3. Results Establishing Correctness of the Algorithm In this section, we present two results that establish that our algorithm is correct; that is, that it produces only minimally 3-connected graphs. According to Theorem 5, when operation D1, D2, or D3 is applied to a set S of edges and/or vertices in a minimally 3-connected graph, the result is minimally 3-connected if and only if S is 3-compatible. To check whether a set is 3-compatible, we need to be able to check whether chording paths exist between pairs of vertices. To check for chording paths, we need to know the cycles of the graph. Since enumerating the cycles of a graph is an NP-complete problem, we would like to avoid it by determining the list of cycles of a graph generated using D1, D2, or D3 from the cycles of the graph it was generated from. To determine the cycles of a graph produced by D1, D2, or D3, we need to break the operations down into smaller “atomic” operations. The first theorem in this section, Theorem 8, expresses operations D1, D2, and D3 in terms of edge additions and vertex splits. The second theorem in this section, Theorem 9, provides bounds on the complexity of a procedure to identify the cycles of a graph generated through operations D1, D2, and D3 from the cycles of the original graph. The second theorem relies on two key lemmas which show how cycles can be propagated through edge additions and vertex splits. We refer to these lemmas multiple times in the rest of the paper.

Theorem 8.Let G be a simple 3-connected graph. Operations D1, D2, and D3 can be expressed as a sequence of edge additions and vertex splits. Specifically:

(a)

D1 applied to a vertex x and an edgeabin G to create a new edgexycan be expressed as(G+e)∘f, wheree=xaandf=ay;

(b)

D2 applied to two edgesabandcdin G to create a new edgexycan be expressed as(G+e)∘{_fc,_fb}, wheree=bc,_fb=xband_fc=cy; and

(c)

D3 applied to vertices x, y and z in G to create a new vertex w and edgesxw,ywandzwcan be expressed as(G+{_e1,_e2})∘f, where_e1=yx,_e2=zxandf=xw.

Proof.

Operation D1 requires a vertex x and a nonincident edgeab. The operation is performed by subdividing edgeabby vertex y, and adding edgexy. We may also interpret this operation as adding an edgee=xa, and then splitting vertex a in such a way that y is the new vertex adjacent to x and b, and the new edgef=ya , as shown in Figure 6. In the process, edgee=xais replaced with a new edge^e′=xyand edgeabis replaced with a new edgeyb. Following this interpretation, the resulting graph is (G+e)∘f.

Operation D2 requires two distinct edgesabandcd , and is performed by subdividing both edges and adding a new edge connecting the two vertices. We may interpret this operation using the following steps, illustrated in Figure 7:

(i)

Add an edgee=bc;

(ii)

split the vertex c in such a way that y is the new vertex adjacent to b and d, and the new edge_fc=yc; and

(iii)

split the vertex b in such a way that x is the new vertex adjacent to a and y, and the new edge_fb=bx.

In step (ii), edgee=bcis replaced with a new edge^e′=yband edgecdis replaced with a new edgeyd. In step (iii), edge^e′=ybis replaced with a new edge^e″=xyandabis replaced with a new edgexa. Following this interpretation, the resulting graph is(G+e)∘{_fc,_fb}.

Operation D3 requires three vertices x, y, and z. The operation is performed by adding a new vertex w and edgesxw,yw, andzw. We may interpret this operation as adding one edge_e1=xy, adding a second edge_e2=xz, and then splitting the vertex x in such a way that w is the new vertex adjacent to y and z, and the new edgef=xw . This is illustrated in Figure 8. Following this interpretation, the resulting graph is(G+{_e1,_e2})∘f.  □

In Theorem 8, it is possible that the initially added edge in each of the sequences above is a parallel edge; however we will see in Section 6 that we can avoid adding parallel edges by selecting our initial “seed” graph carefully.

Consider the function HasChordingPath(G,a,b,K), where G is a graph, a and b are vertices in G and K is a set of edges, whose value is True if there is a chording path from a to b inG\K , and False otherwise. To efficiently determine whether S is 3-compatible, whether S is a set consisting of a vertex and an edge, two edges, or three vertices, we need to be able to evaluate HasChordingPath. To evaluate this function, we need to check all paths from a to b for chording edges, which in turn requires knowing the cycles ofG\K. The second theorem in this section establishes a bound on the complexity of obtaining cycles of a graph from cycles of a smaller graph. The proof consists of two lemmas, interesting in their own right, and a short argument.

Using Theorem 8, we can propagate the list of cycles of a graph through operations D1, D2, and D3 if it is possible to determine the cycles of a graph^G′obtained from a graph G by:

• Adding an edgeuvbetweeen two non-adjacent vertices u and v; and

• Splitting a vertex v in G to form a new vertex^v′of degree 3 that is incident to the new edgef=v^v′and two other edges.

The first lemma shows how the set of cycles can be propagated when an edgeuvis added betweeen two non-adjacent vertices u and v.

Lemma 1 (Cycle Chording Lemma).

Let G be a simple 2-connected graph with n vertices and letC(G)be the set of cycles of G. Let^G′be obtained from G by adding an edgeuvbetween two non-adjacent vertices in G. Then the cycles of^G′consists of:

(i)

C(G); and

(ii)

Cycles

_w1,…,_wi,u,v,_wj+1,…,_wk,_w1

and

u,_wi+1,…,_wj,v,u,

where

_w1,…,_wi,u,_wi+1,…,_wj,v,_wj+1,…,_wk,_w1

is a cycle in G passing through u and v, as shown in Figure 9.

The complexity of determining the cycles of^G′from the cycles of G isO(|C(G)|n).

Proof.

We need only show that any cycle in^G′can be produced by (i) or (ii). Suppose C is a cycle in ^G′. If C does not contain the edgeuvthen C must also be a cycle in G. Otherwise, the edges in C other thanuvform au−vpath_P1in G. Since G is 2-connected, there is another edge-disjointu−vpath_P2in G. Paths_P1and_P2together form a cycle in G, and C can be obtained from this cycle using the operation in (ii) above. Finally, the complexity of determining the cycles of^G′from the cycles of G isO(|C(G)|n)because each cycle has to be traversed once and the maximum number of vertices in a cycle is n. □

The graph G in the statement of Lemma 1 must be 2-connected. It is easy to find a counterexample when G is not 2-connected; adding an edge to a graph containing a bridge may produce many cycles that are not obtainable from cycles in G by Lemma 1 (ii).

Obtaining the cycles when a vertex v is split to form a new vertex^v′of degree 3 that is incident to the new edgef=v^v′and two other edges is more complicated. For the purpose of identifying cycles, we regard a vertex split, where the new vertex has degree 3, as a sequence of two “atomic” operations. Let v be a vertex in a graph G of degree at least 4, and let p, q, r, and s be four other vertices in G adjacent to v. The following two steps describe a vertex split of v in which p and q become adjacent to the new vertex and r and s remain adjacent to v:

• Subdivide the edge joining v and p, adding a new vertex^v′.

• Remove the edgeqvand replace it with a new edgeq^v′.

This is illustrated in Figure 10. By thinking of the vertex split this way, if we start with the set of cycles of G, we can determine the set of cycles ofG∘f, whereG∘fis obtained by splitting vertex v to form a new vertex^v′of degree 3 that is incident to the new edgef=v^v′and two other edges. The cycles of the graph resulting from step (1) above are simply the cycles of G, with any occurrence of the edgepvreplaced with the two edgesp^v′and^v′v. Cycles without the edgepvremain unchanged.

The cycles of the graph resulting from step (2) above are more complicated. Suppose G is a graph and consider three vertices a, b, and c in G whereabandbcare edges, butacis not an edge. Let^G′be the graph formed from G by deleting edgeaband adding edgeac. Think of this as “flipping” the edgeabto the edgeac as shown in Figure 11. Please note that in Figure 10, this corresponds to removing the edgeqvand replacing it with edgeq^v′.

Let C be any cycle in G represented by its vertices in order. We may identify cases for determining how individual cycles are changed whenabis replaced withac , by representing a cycle with a “pattern” that describes where a, b, and c occur in it, if at all. Consider, for example, the cycles of the prism graph with vertices labeled as shown in Figure 12:

{015430,0125430,0152340,0321540,123451,012540,015230,012340,23452,1251,032540,01540,0340,01230}

We identify cycles of the modified graph by following the three steps below, illustrated by the example of the cycle 015430 taken from the prism graph. Eliminate the redundant final vertex 0 in the list to obtain 01543. In this example, leta=1,b=4, andc=3. If none ofa,b,cappear in C, then there is nothing to do since it remains a cycle in^G′.

• Rotate the list so that a appears first, if it occurs in the cycle, or b if it appears, or c if it appears:15430.

• Replace the vertex numbers associated with a, b and c with “a”, “b” and “c”, respectively:a5bc0.

• Replace the first sequence of one or more vertices not equal to a, b or c with a diamond (⋄), the second if it occurs with a triangle (▵) and the third, if it occurs, with a square (□):a⋄bc▵.

It helps to think of these steps as symbolic operations: 15430

a5bc0

a⋄bc▵

There is no square in the above example. If we start with cycle 012543 witha=1,b=5,c=3we get

125430

a2b4c0

a⋄b▵c□

This procedure will produce different results depending on the orientation used when enumerating the vertices in the cycle; we include all possible patterns in the case-checking in the next result for clarity’s sake. Moreover, as explained above, in this representation, ⋄, ▵, and □ simply represent sequences of vertices in the cycle other than a, b, or c; the sequences they represent could be of any length. Finally, unlike Lemma 1, there are no connectivity conditions on Lemma 2.

Lemma 2

(Edge Flip Lemma). Let G be a simple graph with n vertices and letC(G)be the set of cycles of G. Leta,b,c∈V(G)such thatab,bc∈E(G), butac∉E(G). Let^G′be the graph obtained from G by replacingabwith a new edgeac. The complexity of determining the cycles of^G′isO(|C(G)^|2n).

Proof.

The cycles of^G′can be determined from the cycles of G by analysis of patterns as described above. First observe that any cycle in G that does not include at least two of the vertices a, b, and c remains a cycle in^G′. If a cycle of G does contain at least two of a, b, and c, then we can evaluate how the cycle is affected by the flip fromabtoacbased on the cycle’s pattern.

We can enumerate all possible patterns by first listing all possible orderings of at least two of a, b and c:ab,ac,bc,abcandacb, and then for each one identifying the possible patterns. Representing cycles in this fashion allows us to distill all of the cycles passing through at least 2 of a, b and c in G into 6 cases with a total of 16 subcases for determining how they relate to cycles in^G′.

Case 1:ab: A pattern containing a and b may or may not include vertices between a and b, and may or may not include vertices between b and a. This results in four combinations:ab,a⋄b,ab⋄, and a⋄b▵. Of theseabis impossible because G has no parallel edges, and therefore a cycle in G must have three edges. Cycles matching the other three patterns are propagated as follows:

a⋄b: If there is a cycle of the forma⋄bin G as shown in the left-hand side of the diagram, then when the flip is implemented andabis replaced withacinG′,a⋄bcmust be a cycle. In other wordsG′has a cyclea⋄bcin place of cyclea⋄b . (Cycles in the diagram are indicated with dashed lines.)
ab⋄: If there is a cycle of the formab⋄in G, thenG′has a cycleacb⋄, which isab⋄withabreplaced withacb .
a⋄b▵: This cycle remains a cycle inG′ .

Case 2:ac: The possible patterns containing a and c areac,a⋄c,ac⋄, anda⋄c▵. In this case, 3 of the 4 patterns are impossible:acis impossible because G has no parallel edges;ac⋄anda⋄care impossible because a and c are not adjacent. Cycles matching the remaining pattern are propagated as follows:

a⋄c▵:G′has the same cycle as G. Two new cycles emerge also, namely a⋄candac⋄, becauseac chords the cycle.

Case 3:bc: The possible patterns containing b and c arebc,b⋄c,bc⋄, andb⋄c▵. In this case,bcis impossible because G has no parallel edges. Cycles matching the other three patterns are propagated with no change:

b⋄c: This remains a cycle inG′ .
bc⋄: This remains a cycle inG′ .
b⋄c▵: This remains a cycle inG′ .

Case 4:abc: The eight possible patterns containing a, b, and c in order areabc,a⋄bc,ab⋄c,a⋄b▵c,abc⋄,a⋄bc▵,ab⋄c▵, anda⋄b▵c□. In this case, four patterns,abc,a⋄bc,ab⋄c, anda⋄b▵care all impossible because a and c are not adjacent in G. Cycles matching the other four patterns are propagated as follows:

abc⋄: If G has a cycle of the formabc⋄, thenG′has a cycleac⋄, which isabc⋄withabcreplaced withac .
a⋄bc▵: This remains a cycle inG′ .
ab⋄c▵: If G has a cycle of the formab⋄c▵, then it will be replaced inG′with two cycles:b⋄candac▵ .
a⋄b▵c□: This remains a cycle inG′ .

Case 5:acb: The eight possible patterns containing a, c, and b in order areacb,a⋄cb,ac⋄b,a⋄c▵b,acb⋄,a⋄cb▵,ac⋄b▵, anda⋄c▵b□. In this case, four patterns,acb,ac⋄b,acb⋄, andac⋄b▵are impossible because a and c are not adjacent in G. Cycles matching the other four patterns are propagated as follows:

a⋄cb: If G has a cycle of the forma⋄cb, thenG′will have a cycle of the forma⋄c, which is the original cycle withcbareplaced withca .
a⋄c▵b: If G has a cycle of the forma⋄c▵b, thenG′will have cycles of the formb▵canda⋄c in its place.
a⋄cb▵: This remains a cycle inG′ .
a⋄c▵b□: This remains a cycle inG′ .

Case 6: There is one additional case in which two cycles in G result in one cycle in^G′after the flip operation:

Two cycles in G which share the common vertex b, share no other common vertices and for which the edgeablies in one cycle and the edgebclies in the other; that is a pair of cycles with patternsab⋄andb▵c, correspond to one cycle inG′of the forma⋄b▵c .

In all but the last case, an existing cycle has to be traversed to produce a new cycle making it anO(n)operation because a cycle may contain at most n vertices. Without the last case, because each cycle has to be traversed the complexity would beO(|C(G)|n). The last case requires consideration of every pair of cycles which isO(|C(G)^|2n).  □

Now, using Lemmas 1 and 2 we can establish bounds on the complexity of identifying the cycles of a graph obtained by one of operations D1, D2, and D3, in terms of the cycles of the original graph.

Theorem 9.

Let^G′be a simple graph obtained from a smaller 3-connected graph G by one of operations D1, D2, and D3. Let n be the number of vertices in G and let c be the number of cycles of G. Then the cycles of^G′can be obtained from the cycles of G by a method with complexityO(^c2n).

Proof.

Using Theorem 8, operation D1 can be expressed as an edge addition, followed by an edge subdivision, followed by an edge flip. By Lemmas 1 and 2, the complexities for these individual steps areO(cn),O(c), andO(^c2n), respectively, so the overall complexity isO(^c2n). Similarly, operation D2 can be expressed as an edge addition, followed by two edge subdivisions and edge flips, and operation D3 can be expressed as two edge additions followed by an edge subdivision and an edge flip, so the overall complexity of propagating the list of cycles for D2 and D3 is alsoO(^c2n).  □

4. Cycle Propagation Algorithm

To check when operations D1, D2, and D3 can be performed, we must check for chording paths between specific vertices. Let G be a graph with n vertices and letCdenote its set of cycles. Since we will be considering only one input graph at a time, in this sectionC is unambiguous. Given the set of cycles of the input graph G, Lemmas 1 and 2 allow us to define three procedures ApplyFlipEdge, ApplyAddEdge, and ApplySubdivideEdge, which compute the set of cycles of a graph modified by flipping an edge, adding an edge, or subdividing an edge. This allows us to propagate the set of cycles for the new graphs we produce in terms of the cycles of G, which in turn allows us to avoid the NP-complete problem of computing all the cycles of a graph.

The procedures described in this section rely on two simpler procedures, ChordCycle and Chords, which are defined informally below.

• ChordCycle(C,_v1,_v2): This is the procedure described in Lemma 1. Given a cycle C and a pair of vertices_v1and_v2which both occur in the cycle, but are not adjacent, return a pair of cycles generated as follows: The first cycle is created by starting at_v1, then proceeding to_v2, and then following the existing cycle from_v2back to_v1. The second cycle begins with_v1and proceeds along the existing cycle until_v2is reached, and then returns to_v1. That is, if the existing cycle consists of vertices

  _w1,_w2,…,_wi,_v1,_wi+1,…,_wj,_v2,_wj+1,…,_wk,

  then the two new cycles will consist of vertices

  _v2,_wj+1,…,_wk,_w1,…,_v1

  and

  _v1,_wi+1,…,_wj,_v2.

  Its complexity isO(n).

• Chords(C,_v1,_v2): This procedure simply determines whether an edge chords a cycle. Given a cycle C and two vertices_v1and_v2, determine whether there is an edge_{v1 v2}that chords C. Its complexity isO(n).

Next, we present the three procedures ApplyFlipEdge, ApplyAddEdge and ApplySubdivideEdge, respectively.

• ApplyFlipEdge(C,a,b,c): This procedure is also described informally, as its steps closely follow the cases in the proof of Lemma 2. Given the setCof cycles of a graph G and vertices a, b, and c with edgesabandbc, but no edgeac , ApplyFlipEdge generates the list of cycles of the graph^G′produced by replacing edgeabwith a new edgeac, using the procedure outlined with Lemma 2. Its complexity isO(|C^|2n).

• ApplyAddEdge(C,a,b): This procedure computes the resulting cycles when adding an edge to a graph, whereC is the set of cycles and a and b are two non-adjacent vertices. It creates the new set of cycles by adding the cycles from the old graph and the new cycles created by ChordCycle for any cycle that is chorded byab. Its complexity isO(|C|n) . Pseudocode is shown in Algorithm 1.

  Algorithm 1 Compute cycles for an edge addition

  1.   procedure ApplyAddEdge(C,a,b)

  2.S←ϕ

  3.   forC∈Cdo

  4.S←S∪{C}

  5.    ifChords(C,a,b)then

  6.C1,C2←ChordCycle(C,a,b)

  7.S←S∪{C1,C2}

  8.    end if

  9.   end for

  10.  end procedure

• ApplySubdivideEdge(C,a,b,c): This procedure computes cycles resulting when subdividing an edge, whereCis the set of cycles of the graph, a and b are two adjacent vertices, and vertex c is being added to subdivide the edgeab. Its complexity isO(|C|n) . Pseudocode is shown in Algorithm 2.

  Algorithm 2 Compute cycles for subdividing an edge

  1:  procedure ApplySubdivideEdge(C, a, b, c)

  2:S←ϕ

  3:   forC∈Cdo

  4:    if C contains edge(ab)then

  5:     Add cycle C witha,breplaced witha,c,bto S

  6:    else

  7:     Add C to S

  8:    end if

  9:   end for

  10:  end procedure

5. Isomorph-Free Graph Construction This section is further broken into three subsections. 5.1. Organizing Graph Construction to Minimize Isomorphism Checking When we apply operation D1 to a graph, we end up with a graph that has two more edges and one more vertex. When we apply operation D2 to a graph, we end up with a graph that has three more edges and two more vertices. When we apply operation D3 to a graph, we end up with a graph that has three more edges and one more vertex. This creates a problem if we want to avoid generating isomorphic graphs, because we have to keep track of graphs of different sizes at the same time. To prevent this, we want to focus on doing everything we need to do with graphs with one particular number of edges and vertices all at once. In particular, if we consider operations D1, D2, and D3 as algorithms, then:

• D1 takes a graph G with n vertices and m edges, a vertexx∈V(G)and an edgeab∈E(G)as input, and produces a graph^G′=(G+e)∘_fcwithn+1vertices andm+2edges (see Theorem 8 (i));

• D2 takes a graph G with n vertices and m edges, and two edgesab,cd∈E(G)as input, and produces a graph^G′=(G+e)∘{_fc,_fb}withn+2vertices andm+3edges (see Theorem 8 (ii)); and

• D3 takes a graph G with n vertices and m edges, and three verticesx,y,z∈V(G)as input, and produces a graph^G′=(G+{_e1,_e2})∘fwithn+1vertices andm+3edges (see Theorem 8 (iii)).

Figure 13 outlines the process of applying operations D1, D2, and D3 to an individual graph. The specific procedures E1, E2, C1, C2, and C3 will be detailed in Section 5.3.

To avoid generating graphs that are isomorphic to each other, we wish to maintain a list of generated graphs and check newly generated graphs against the list to eliminate those for which isomorphic duplicates have already been generated. We immediately encounter two problems with this approach: checking whether a pair of graphs is isomorphic is a computationally expensive operation; and the number of graphs to check grows very quickly as the size of the graphs, both in terms of vertices and edges, increases.

The first problem can be mitigated by using McKay’s nauty system [10] (available for download at http://pallini.di.uniroma1.it/) to generate certificates for each graph. The nauty certificate functionϕproduces a data artifact from a graph in such a way thatϕ(_G1)=ϕ(_G2)if and only if_G1≅_G2. Thus we can reduce the problem of checking isomorphism to the problem of generating certificates, and then compare a newly generated graph’s certificate to the set of certificates of graphs already generated.

The second problem can be mitigated by a change in perspective. While Figure 13 demonstrates how a single graph will be treated by our process, consider Figure 14, which we refer to as the “infinite bookshelf”. As the entire process of generating minimally 3-connected graphs using operations D1, D2, and D3 proceeds, with each operation divided into individual steps as described in Theorem 8, the set of all generated graphs with n vertices and m edges will contain both “finished”, minimally 3-connected graphs, and “intermediate” graphs generated as part of the process. What does this set of graphs look like?

• For operation D1, the set may include graphs of the formG+_e1, where G has n vertices andm−1edges, and graphs of the form(G+_e1)∘f, where G hasn−1vertices andm−2edges.

• For operation D2, the set may include graphs of the formG+_e1, where G has n vertices andm−1edges, graphs of the form(G+_e1)∘f, where G hasn−1vertices andm−2edges, and graphs of the form(G+_e1)∘{_fc,_fb}, where G hasn−2vertices andm−3edges.

• For operation D3, the set may include graphs of the formG+_e1where G has n vertices andm−1edges, graphs of the formG+{_e1,_e2}, where G has n vertices andm−2edges, and graphs of the form(G+{_e1,_e2})∘f, where G hasn−1vertices andm−3edges.

When generating graphs, by storing some data along with each graph indicating the steps used to generate it, and by organizing graphs into subsets, we can generate all of the graphs needed for the algorithm with n vertices and m edges in one batch. Organized in this way, we only need to maintain a list of certificates for the graphs generated for one “shelf”, and this list can be discarded as soon as processing for that shelf is complete. We do not need to keep track of certificates for more than one shelf at a time.

Section 5.2 breaks down the graphs in one shelf formally by their place in operations D1, D2, and D3. Section 5.3 then describes how the procedures for each shelf work and interoperate.

5.2. The Algorithm Is Isomorph-Free

To make the process of eliminating isomorphic graphs by generating and checking nauty certificates more efficient, we organize the operations in such a way as to be able to work with all graphs with a fixed vertex count n and edge count m in one batch. Specifically, for anm,ncombination, we define sets_Am,n(*), where * represents 0, 1, 2, or 3,_Bm,nand_Cm,nas follows:

• _Am,n(0)only ever contains of the “root” graph; i.e., the prism graph. So for values of m and n other than 9 and 6,_Am,n(0)=⌀. All graphs in_Am,n(0),_Am,n(1),_Am,n(2), and_Am,n(3)are minimally 3-connected.

• _Bm,nconsists of graphs generated by adding an edge to a minimally 3-connected graph withm−1vertices and n edges.

• _Cm,nconsists of graphs generated by adding an edge to a graph in_Bm−1,nthat is incident with the edge added to form the input graph.

• _Am,n(1)consists of graphs generated by splitting a vertex in a graph in_Bm−1,n−1that is incident to the edge added to form the input graph, after checking for 3-compatibility.

• _Am,n(2)consists of graphs generated by splitting a vertex in a graph in_{Am−1,n−1(1)}that is incident to the same edge as the vertex split to form the input graph, after checking for 3-compatibility.

• _Am,n(3)consists of graphs generated by splitting a vertex in a graph in_Cm−1,n−1that is incident to the two edges added to form the input graph, after checking for 3-compatibility.

Then, beginning withm=10andn=6, we construct graphs in_Cm,n,_Bm,n,_Am,n(1),_Am,n(2)and_Am,n(3), in that order, from input graphs withm−1vertices and n edges, and withm−1vertices andn−1 edges. As graphs are generated in each step, their certificates are also generated and stored. Any new graph with a certificate matching another graph already generated, regardless of the step, is discarded, so that the full set of generated graphs is pairwise non-isomorphic. At the end of processing for one value of n and m the list of certificates is discarded.

For any value of n, we can start withm=n+4and proceed until no more graphs or generated or, whenn≥8, whenm=3n−7. By Theorem 3, no further minimally 3-connected graphs will be found afterm=3n−9whenn≥8; however we still need to generate single- and double-edge additions to be used when considering graphs withn+1 vertices. Proceeding in this fashion, at any time we only need to maintain a list of certificates for the graphs for one value of m and n. The generation sources and targets are summarized in Figure 15, which shows how the graphs with n vertices and m edges, in the upper right-hand box, are generated from graphs with n vertices andm−1edges in the upper left-hand box, and graphs withn−1vertices andm−1edges in the lower left-hand box.

5.3. Infinite Bookshelf Algorithm

This subsection contains a detailed description of the algorithms used to generate graphs, implementing the process described in Section 5.2.

The process of computing(G+e)∘_fc,(G+e)∘{_fc,_fb}, and(G+{_e1,_e2})∘f is broken down into individual procedures E1, E2, C1, C2, and C3, each of which operates on an input graph with one less edge, or one less edge and one less vertex, than the graphs it produces. The procedures are implemented using the following component steps, as illustrated in Figure 13:

• Procedure E1 is applied to graphs in_Am−1,n(*), which are minimally 3-connected, to generate all possible single edge additionsG+e given an input graph G. This is the first step for operations D1, D2, and D3, as expressed in Theorem 8. The cycles of the output graphs are constructed from the cycles of the input graph G (which are carried forward from earlier computations) using ApplyAddEdge. The results, after checking certificates, are added to_Bm,n.

• Procedure E2 is applied to graphs in_Bm−1,nand treats an input graph as G+_e1 in operation D3, as expressed in Theorem 8. It adds all possible edges with a vertex in common to the edge added by E1 to yield a graphG+{_e1,_e2} . This is the second step in operation D3 as expressed in Theorem 8. Cycles in these graphs are also constructed using ApplyAddEdge. The results, after checking certificates, are added to_Cm,n.

• Procedure C1 is applied to graphs in_Bm−1,n−1and treats an input graph asG+eas defined in operations D1 and D2, as expressed in Theorem 8. It generates two splits(G+e)∘f for each input graph, one for each of the vertices incident to the edge added by E1. This is the second step in operations D1 and D2, and it is the final step in D1. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to_Am,n(1). This procedure only produces splits for graphs for which the original set of vertices and edges is 3-compatible, and as a result it yields only minimally 3-connected graphs.

• Procedure C2 is applied to graphs in_{Am−1,n−1(1)}and treats an input graph as(G+e)∘_fcas defined in operation D2, as expressed in Theorem 8. It generates splits(G+e)∘{_fc,_fb} of the remaining un-split vertex incident to the edge added by E1. This is the third step of operation D2 when the new vertex is incident with e; otherwise it comprises another application of D1. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to_Am,n(2). This procedure only produces splits for 3-compatible input sets, and as a result it yields only minimally 3-connected graphs.

• Procedure C3 is applied to graphs in_Cm−1,n−1and treats an input graph asG+{_e1,_e2}as defined in operation D3 as expressed in Theorem 8. For each input graph, it generates one vertex split(G+{_e1,_e2})∘f of the vertex common to the edges added by E1 and E2. It uses ApplySubdivideEdge and ApplyFlipEdge to propagate cycles through the vertex split. The results, after checking certificates, are added to_Am,n(3). This procedure only produces splits for 3-compatible input sets, and as a result it yields only minimally 3-connected graphs.

While C1, C2, and C3 produce only minimally 3-connected graphs, they may produce different graphs that are isomorphic to one another. We use Brendan McKay’s nauty to generate a canonical label for each graph produced, so that only pairwise non-isomorphic sets of minimally 3-connected graphs are ultimately output.

The following procedures are defined informally:

• AddEdge(G,u,v)—Given a graph G and a pair of vertices u and v in G, this procedure returns a graph^G′ formed from G by adding an edge connecting u and v. When it is used in the procedures in this section, we also use ApplyAddEdge immediately afterwards, which computes the cycles of the graph with the added edge. The complexity of AddEdge isO(ⁿ²)because the set of edges of G must be copied to form the set of edges of^G′.

• SplitVertex(G,v,u,w)—Given a graph G, a vertex v and two edgesvuandvw, this procedure returns a graph^G′formed from G by adding a vertex^v′, adding an edge connecting v and^v′, and replacing the edgesvuandvwwith edges^v′uand^v′w . When it is used in the procedures in this section, we also use ApplySubdivideEdge and ApplyFlipEdge, which compute the cycles of the graph with the split vertex. The complexity of SplitVertex isO(ⁿ²), again because a copy of the graph must be produced.

• NoChordingPaths(C,G,P,X)—Given the setCof cycles of a graph G, a set P of pairs of vertices and another set X of edges, this procedure determines whether there are any chording paths connecting pairs of vertices in P inG\X. Its complexity isO(|C|ⁿ³), as it requires all simple paths between two vertices to be enumerated, which isO(ⁿ²) . This function relies on HasChordingPath as defined in Section 3.

The rest of this subsection contains a detailed description and pseudocode for procedures E1, E2, C1, C2 and C3. The worst-case complexity for any individual procedure in this process is the complexity of C2:O(|C^{|2 n3}).

Procedure E1 is responsible for implementing the first step of operations D1, D2, and D3. It generates all single-edge additions of an input graph G, using ApplyAddEdge to propagate the list of cycles. Its complexity isO(|C|ⁿ³) , as it requires each pair of vertices of G to be checked, and for each non-adjacent pair ApplyAddEdge is used to propagate cycles. Pseudocode is shown in Algorithm 3.

Algorithm 3 First edge addition procedure

1: procedure E1 (G,C)

2:S←ϕ

3:  foru∈V(G)do

4:   forv∈V(G)\udo

5:    ifuv∉E(G)then

6:G′← AddEdge(G,u,v)

7:C′← ApplyAddEdge(C,u,v)

8:S←S∪{(G′,C′,uv)}

9:    end if

10:   end for

11:  end for

12:  return S

13: end procedure

Procedure E2 is responsible for implementing the second step of operation D3. It also generates single-edge additions of an input graph, but under a certain condition. Specifically, given an input graphG=H+_e1with cyclesC , as produced by E1, E2 produces all graphsH+{_e1,_e2}, where the new edge_e2is adjacent to_e1. Its complexity isO(|C|ⁿ²) , as ApplyAddEdge is used every time a new graph is generated, and each vertex is checked for eligibility. Pseudocode is shown in Algorithm 4.

Algorithm 4 Second edge addition procedure

1: procedure E2(G, u, v,C)

2:S←ϕ

3:  forw∈V(G)do

4:   ifwu∉E(G)then

5:G′← AddEdge(G,u,w)

6:C′← ApplyAddEdge(C,u,w)

7:S←S∪{(G′,C′,uw)}

8:   end if

9:   ifwv∉E(G)then

10:G′← AddEdge(G,w,v)

11:C′← ApplyAddEdge(C,w,v)

12:S←S∪{(G′,C′,wv)}

13:   end if

14:  end for

15:  return S

16: end procedure

Procedure C1 is responsible for implementing the second step of operations D1 and D2. These steps are illustrated in Figure 6 and Figure 7, respectively, though a bit of bookkeeping is required to see how C1 corresponds to those operations. C1 starts with a graphG=H+e generated by E1; letbcdenote the added edge. Observe that the chording path checks are made in H, which isG\bc.

First, for any vertexa∈N(b)\cin G, where there are no chordingc−aorb−cpaths inG\{bc,ba}=H\ba , we split b to add a new vertex x adjacent to a, b, and c. This is the same as the second step illustrated in Figure 6 with c, b, a, and x in C1 corresponding to x, a, b, and y in the figure, respectively. It is also the same as the second step illustrated in Figure 7, with c, b, a, and x in C1 corresponding to b, c, d, and y in the figure, respectively.

Second, we must consider splits of the other end vertex of the newly added edge e, namely c. For any vertexd∈N(c)\bin G where there are no chordingb−dorb−cpaths inG\{bc,cd}=H\cd , we split c to add a new vertex y adjacent to b, c, and d. This is the same as the second step illustrated in Figure 6 with b, c, d, and y in C1 corresponding to x, a, b, and y in the figure, respectively. It is also the same as the second step illustrated in Figure 7, with b, c, d, and y in C1 corresponding to b, c, d, and y in the figure, respectively.

Since C1 must makeO(n) calls to ApplyFlipEdge, wheren=|V(G)|, its complexity isO(|C^{|2 n2}) . Pseudocode is shown in Algorithm 5.

Algorithm 5 First vertex split procedure

1: procedureC1(G, b, c,C)

2:S←ϕ

3:  fora∈N(b)\c do                ▹ Split b

4:   if NoChordingPaths(C,G,{(c,a),(b,c)},{bc,ba})then

5:G′,x← SplitVertex(G,b,c,a)

6:C′← ApplySubdivideEdge(C,b,c,x)

7:C′← ApplyFlipEdge(C′,a,b,x)

8:S←S∪{(G′,C′,b,c,a,x)}

9:   end if

10:  end for

11:  ford∈N(c)\b do                ▹ Split c

12:   if NoChordingPaths(C,G,{(b,d),(c,b)},{bc,cd})then

13:G′,y← SplitVertex(G,c,b,d)

14:C′← ApplySubdivideEdge(C,c,b,y)

15:C′← ApplyFlipEdge(C′,d,c,y)

16:S←S∪{(G′,C′,c,b,d,y)}

17:   end if

18:  end for

19:  return S

20: end procedure

Procedure C2 is responsible for implementing the third step in operation D2, as illustrated in Figure 7. It starts with a graphG=(H+e)∘f generated by C1; we denote^e′and f shown in the figure asybandyc , respectively. d represents the third vertex that becomes adjacent to the new vertex in C1, so d and y are also adjacent.

First, for any vertex a adjacent to b other than c, d, or y, for which there are noc−a,c−b,d−b, ord−achording paths inG\{ab,by,cy,dy} , we split b to add a new vertex x adjacent to b, a and y. This is the same as the third step illustrated in Figure 7.

Second, for any pair of vertices a and k adjacent to b other than c, d, or y, and for which there are nok−aork−bchording paths inG\{ab,by,cy,dy}, we split b to add a new vertex x adjacent to b, a and k (leaving y adjacent to b, unlike in the first step).

Since C2 must makeO(ⁿ²) calls to ApplyFlipEdge, wheren=|V(G)|, its complexity isO(|C^{|2 n3}) . Pseudocode is shown in Algorithm 6.

Algorithm 6 Second vertex split procedure

1: procedure C2(G,C,c,b,d,y)

2:S←ϕ

3:  fora∈N(b)\{c,d,y} do            ▹ Final step of Operation (c)

4:   if NoChordingPaths(C,G,{(c,a),(c,b),(d,b),(d,a)},{ab,by,cy,dy})then

5:G′,x← SplitVertex(G,b,y,a)

6:C′← ApplySubdivideEdge(C,b,a,x)

7:C″← ApplyFlipEdge(C′,y,b,x)

8:S←S∪{(G′,C″)}

9:   end if

10:  end for

11:  fora,k∈N(b)\{c,d,y} do          ▹ Final step of Operation (d)

12:   if NoChordingPaths(C,G,{(k,a),(k,b)},{ab,by,cy,dy})then

13:G′,x← SplitVertex(G,b,k,a)

14:C′← ApplySubdivideEdge(C,b,a,x)

15:C″← ApplyFlipEdge(C′,k,b,x)

16:S←S∪{(G′,C″)}

17:   end if

18:  end for

19:  return S

20: end procedure

Procedure C3 is responsible for implementing the third step in operation D3, as illustrated in Figure 8. It starts with a graphG=H+{_e1,_e2} generated by E2, where_e1=xyand_e2=xzare two incident edges. A single new graph is generated in which x is split to add a new vertex w adjacent to x, y and z, if there are nox−y,x−z, ory−zchording paths inG\{xy,xz}=H . Because C3 makes one call to ApplyFlipEdge, its complexity isO(|C^|2n). Pseudocode is shown in Algorithm 7.

Algorithm 7 Third vertex split procedure

1: procedureC3(G,C,x,y,z) 2: S←ϕ 3: if NoChordingPaths(C,G,{(x,y),(x,z),(y,z)},{xy,xz})then 4: G′,w← SplitVertex(G,x,y,z) 5: C′← ApplySubdivideEdge(C,x,z,w) 6: C′← ApplyFlipEdge((C′,y,x,w) 7: S←S∪{(G′,C′)} 8: end if 9: return S 10: end procedure

6. The Algorithm Is Exhaustive

Theorem 5 and Theorem 6 (Dawes’ results) state that, if G is a minimally 3-connected graph and^G′is obtained from G by applying one of the operations D1, D2, and D3 to a set S of vertices and edges, then^G′is minimally 3-connected if and only if S is 3-compatible, and also that any minimally 3-connected graph other than_W3can be obtained from a smaller minimally 3-connected graph by applying D1, D2, or D3 to a 3-compatible set. This shows that application of these operations to 3-compatible sets of edges and vertices in minimally 3-connected graphs, starting with_W3, will exhaustively generate all such graphs. However, as indicated in Theorem 9, in order to maintain the list of cycles of each generated graph, we must express these operations in terms of edge additions and vertex splits.

Consider the graph_W3 itself, as shown in Figure 16. Observe that{x,ab}is a 3-compatible set because there are clearly no chordingxa- orxb-paths in_W3\ab, so we may apply D1 to produce another minimally 3-connected graph, which is actually_W4as shown in the figure. However, since there are already edgesxaandxbin the graph, if we are to apply our step-by-step procedure to accomplish the same thing, we will be required to add a parallel edge. We would like to avoid this, and we can accomplish that by beginning with the prism graph instead of_W3. We are now ready to prove the third main result in this paper.

Theorem 10.Let G be a simple minimally 3-connected graph. Then one of the following statements is true:

1.

G≅_Wn−1forn≥5and G can be obtained from_Wn−2by applying operation D1 to the spoke vertex x and a rim edgeab;

2.

G≅_K3,n−3forn≥7and G can be obtained from_K3,n−4by applying operation D3 to the 3 vertices in the smaller class; or

3.

G has a prism minor, forn≥7, and G can be obtained from a smaller minimally 3-connected graph^G′with a prism minor, where|E(G)|−|E(^G′)|≤3, using operation D1, D2, or D3.

Proof.

Theorem 2 characterizes the 3-connected graphs without a prism minor. Of these, the only minimally 3-connected ones are_Wn−1forn≥4and_K3,n−3forn≥6. Observe that forn≥5,_Wn−1\e/f=_Wn−2, where e is a spoke and f is a rim edge, such thate,fare incident to a degree 3 vertex. Therefore_Wn−1can be obtained from_Wn−2by applying operation D1 to the spoke vertex x and a rim edgeab. The set{x,ab}is 3-compatible because any chording edge of a cycle in_Wn−2\abwould have to be a spoke edge, and since all rim edges have degree three the chording edge cannot be extended into axa- orxb-path.

Observe that, forn≥7,_K3,n−3−w=_K3,n−4, where w is a degree 3 vertex. Therefore,_K3,n−3 can be obtained from a smaller minimally 3-connected graph of the same family by applying operation D3 to the three vertices in the smaller class. The set of three vertices is 3-compatible because the degree of each vertex in the larger class is exactly 3, so that any chording edge cannot be extended into a chording path connecting vertices in the smaller class, as illustrated in Figure 17.

If G has a prism minor, by Theorem 7, with the prism graph as H, G can be obtained from a 3-connected graph withn−1vertices andm−1edges via an edge addition and a vertex split, from a graph withn−2vertices andm−3edges via two edge additions and a vertex split, or from a graph withn−1vertices andm−3edges via an edge addition and two vertex splits; that is, by operation D1, D2, or D3, respectively, as expressed in Theorem 8. By Theorem 6, all minimally 3-connected graphs can be obtained from smaller minimally 3-connected graphs by applying these operations to 3-compatible sets. □

We constructed all non-isomorphic minimally 3-connected graphs up to 12 vertices using a Python implementation of these procedures. The total number of minimally 3-connected graphs for 4 through 12 vertices is published in the Online Encyclopedia of Integer Sequences. Table 1 below lists these values. These numbers helped confirm the accuracy of our method and procedures.

The number of non-isomorphic 3-connected cubic graphs of size n, where n is even, is published in the Online Encyclopedia of Integer Sequences as sequence A204198. This sequence only goes up ton=14 . We were able to obtain the set of 3-connected cubic graphs up to 20 vertices as shown in Table 2.

All of the minimally 3-connected graphs generated were validated using a separate routine based on the Python iGraph (https://igraph.org/python/) vertex_disjoint_paths method, in order to verify that each graph was 3-connected and that all single edge-deletions of the graph were not. The overall number of generated graphs was checked against the published sequence on OEIS.

The 3-connected cubic graphs were verified to be 3-connected using a similar procedure, and overall numbers for up to 14 vertices were checked against the published sequence on OEIS. The minimally 3-connected graphs were generated in 31 h on a PC with an Intel Core I5-4460 CPU at 3.2 GHz and 16 Gb of RAM. The 3-connected cubic graphs were generated on the same machine in five hours.

The algorithm’s running speed could probably be reduced by running parallel instances, either on a larger machine or in a distributed computing environment. MapReduce, or a similar programming model, would need to be used to aggregate generated graph certificates and remove duplicates. It is also possible that a technique similar to the canonical construction paths described by Brinkmann, Goedgebeur and McKay [11] could be used to reduce the number of redundant graphs generated.

Even with the implementation of techniques to propagate cycles, the slowest part of the algorithm is the procedure that checks for chording paths. It may be possible to improve the worst-case performance of the cycle propagation and chording path checking algorithms through appropriate indexing of cycles.

The code, instructions, and output files for our implementation are available at https://github.com/rkingan/m3c. The output files have been converted from the format used by the program, which also stores each graph’s history and list of cycles, to the standard graph6 format, so that they can be used by other researchers.

The authors would like to thank the referees and editor for their valuable comments which helped to improve the manuscript.

n	Minimally 3-Connected Graphs (A199676)
6	3
7	5
8	18
9	57
10	285
11	1513
12	9824

n	3-Connected Cubic Graphs
8	4
10	14
12	57
14	341
16	2828
18	30,468
20	396,150

Author Contributions

All authors contributed equally to this work. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

All data and source code related to this research is available for download at https://github.com/rkingan/m3c.

Conflicts of Interest

The authors declare no conflict of interest.