1. Introduction
In this paper, we present an algorithm for consecutively generating minimally 3connected graphs, beginning with the prism graph, with the exception of two families. The two exceptional families are the wheel graph with
n vertices and
$n1$ spokes denoted by
${W}_{n1}$ for
$n\ge 4$ and the complete bipartite graph with 3 vertices in one class and
$n3$ vertices in the other class denoted by
${K}_{3,n3}$ for
$n\ge 6$. See
Figure 1.
Tutte proved that a simple graph is 3connected if and only if it is a wheel or is obtained from a wheel by adding edges between nonadjacent vertices and splitting vertices [
1]. The vertex split operation is illustrated in
Figure 2. At each stage the graph obtained is 3connected.
A cubic graph is a graph whose vertices have degree 3. Let
G and
H be 3connected cubic graphs such that
$G\ncong {W}_{3}$ 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 3connected and cubic [
2]. Observe that this operation is equivalent to adding an edge
$e=uv$ to a cubic graph and splitting
u and splitting
v. This gives an easy way of consecutively constructing all 3connected cubic graphs on
n vertices for even
n. Surprisingly the entry for the number of 3connected cubic graphs in the Online Encyclopedia of Integer Sequences (sequence A204198) has entries only up to
$n=14$. We were able to quickly obtain such graphs up to
$n=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 3connected graphs.
Dawes gave a necessary and sufficient characterization for the construction of minimally 3connected graphs starting with
${W}_{3}$. To do this he needed three operations one of which is the above operation where two distinct edges are bridged. Let
$e=ab$ be an edge and
$x\ne a,b$ be 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
${W}_{3}$ the class of minimally 3connected 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 “3compatible 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 3connected graphs from smaller minimally 3connected 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 NPcomplete 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}^{\prime}$ obtained from a graph G by edge additions and vertex splits, and Dawes specifications on 3compatible 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}^{\prime}$ can be obtained from the set of cycles of G by a method with complexity $\mathcal{O}\left({c}^{2}n\right)$. Third, we prove that if G is a minimally 3connected graph that is not ${W}_{n1}$ for $n\ge 4$ or ${K}_{3,n3}$ for $n\ge 6$, then G must have a prism minor, for $n\ge 7$, and G can be obtained from a smaller minimally 3connected graph ${G}^{\prime}$ such that $\leftE\left(G\right)\rightE\left({G}^{\prime}\right)\le 3$ using edge additions and vertex splits and Dawes specifications on 3compatible sets.
We present an algorithm based on the above results that consecutively constructs the nonisomorphic minimally 3connected graphs with n vertices and m edges from the nonisomorphic minimally 3connected graphs with $n1$ vertices and $m2$ edges, $n1$ vertices and $m3$ edges, and $n2$ vertices and $m3$ edges. This formulation also allows us to determine worstcase complexity for processing a single graph; namely $\mathcal{O}\left({c}^{2}{n}^{3}\right)$, which includes the complexity of cycle propagation mentioned above.
There has been a significant amount of work done on identifying efficient algorithms for certifying 3connectivity of graphs. Hopcroft and Tarjan published a lineartime algorithm for testing 3connectivity [
3]. Schmidt extended this result by identifying a certifying algorithm for checking 3connectivity in linear time [
4]. The perspective of this paper is somewhat different. Instead of checking an existing graph to determine whether it is minimally 3connected, we seek to construct graphs from the prism using a procedure that generates only minimally 3connected graphs. The algorithm presented in this paper is the first to generate exclusively minimally 3connected graphs from smaller minimally 3connected 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 and $e=uv$ be an edge with end vertices u and v. The graph with edge e deleted is called an edgedeletion and is denoted by $G\backslash e$ or $G\backslash 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 edgecontraction and denoted by $G/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 write $H=G\backslash 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 3connected if at least 3 vertices must be removed to disconnect the graph. In a 3connected graph G, an edge e is deletable if $G\backslash e$ remains 3connected. A 3connected graph with no deletable edges is called minimally 3connected.
There are multiple ways that deleting an edge in a minimally 3connected 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 2connected graph that is not 3connected. Halin proved that a minimally 3connected graph has at least one triad [
5]. We exploit this property to develop a construction theorem for minimally 3connected graphs.
The operation that reverses edgedeletion is edge addition. A simple graph G with an edge $e=uv$ added between nonadjacent vertices is called an edge addition of G and denoted by $G+e$ or $G+uv$.
The operation that reverses edgecontraction is called a vertex split of G. To split a vertex v with $de{g}_{G}\left(v\right)\ge 4$, first divide ${N}_{G}\left(v\right)$ into two disjoint sets S and T, both of size at least 2. Then replace v with two distinct vertices v and ${v}^{\prime}$, join them by a new edge $f=v{v}^{\prime}$, and join each neighbor of v in S to v and each neighbor in T to ${v}^{\prime}$. The resulting graph is called a vertex split of G and is denoted by $K=G{\circ}_{S,T}f$. In other words ${N}_{G}\left(v\right)$ is partitioned into two sets S and T, and in K, ${N}_{K}\left(v\right)=S\cup {v}^{\prime}$ and ${N}_{K}\left({v}^{\prime}\right)=T\cup v$. Observe that $de{g}_{K}\left(v\right)\ge 3$ and $de{g}_{K}\left({v}^{\prime}\right)\ge 3$.
We can get a different graph depending on the assignment of neighbors of
v in
G to
v and
${v}^{\prime}$ in the vertex split; hence the sets
S and
T in the notation. With a slight abuse of notation, we can say
$G\circ f$, as each vertex split is described with a particular assignment of neighbors of
v in
G to
v and
${v}^{\prime}$. When performing a vertex split, we will think of
${v}^{\prime}$ as the new vertex that gets added and
$f=v{v}^{\prime}$ as the new edge that gets added. Observe that if
G is 3connected, then edge additions and vertex splits remain 3connected. The degree condition
$de{g}_{G}\left(v\right)\ge 4$ is not necessary for an arbitrary vertex split, but required to preserve 3connectivity.
Figure 2 shows the vertex split operation.
In 1961 Tutte proved that a simple graph is 3connected 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 3connected 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 3connected graphs without a prism minor [
6]. The graphs
${K}_{3,n3}^{\prime}$,
${K}_{3,n3}^{\u2033}$, and
${K}_{3,n3}^{\u2034}$ are obtained from the complete bipartite graph
${K}_{3,n3}$ (shown in
Figure 1) with one, two, or three edges, respectively, joining the three vertices in one class.
Theorem 2 (Dirac, 1963)
. A simple 3connected graph G has no prismminor if and only if G is isomorphic to ${K}_{5}\backslash e$, ${K}_{5}$, ${W}_{n1}$, for $n\ge 4$, ${K}_{3,n3}$, ${K}_{3,n3}^{\prime}$, ${K}_{3,n3}^{\u2033}$, or ${K}_{3,n3}^{\u2034}$, for $n\ge 6$.
Theorem 2 implies that there are only two infinite families of minimally 3connected graphs without a prismminor, namely ${W}_{n1}$ for $n\ge 4$ and ${K}_{3,n3}$ for $n\ge 6$. Thus, we may focus on constructing minimally 3connected graphs with a prism minor.
Next, Halin proved that minimally 3connected 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 3connected graph on $n\ge 8$ vertices. Then $\leftE\right(G\left)\right\le 3n9$. Moreover, $\leftE\right(G\left)\right=3n9$ if and only if $G\cong {K}_{3,n3}$.
In 1969 Barnette and Grünbaum defined two operations based on subdivisions and gave an alternative construction theorem for 3connected 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 3connected graph. The first Barnette and Grünbaum operation is defined as follows: Subdivide an edge
$ab$ by vertex
y and add edge
$xy$ for a vertex
$x\ne 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 edges
$ab$ and
$cd$, by vertices
x and
y, respectively, and add edge
$xy$. This is what we called “bridging two edges” in
Section 1. Observe that these operations, illustrated in
Figure 3, preserve 3connectivity.
Theorem 4 (Barnette and Grünbaum, 1968)
. Let G be a simple graph such that $G\ncong {W}_{3}$. Then G is 3connected if and only if G can be constructed from ${W}_{3}$ by 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 3connected graphs starting with
${W}_{3}$. 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 vertices
$x,y,z$ in the graph and link all three to a new vertex
w by adding three new edges
$xw$,
$yw$, and
$zw$. Observe that this new operation also preserves 3connectivity. 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 3connected 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 3connected graph and applies one of these operations, the resulting graph will also be minimally 3connected if and only if certain conditions are met. Let
C be a cycle in a graph
G. A
chord of
C is an edge
$e\notin 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 3connected. A set S of vertices and/or edges in a graph G is 3compatible if it conforms to one of the following three types:
$S=\{x,ab\}$, where x is a vertex of G, $ab$ is an edge of G, $x\ne a,b$ and no $xa$path or $xb$path is a chording path of $Gab$;
$S=\{ab,cd\}$, where $ab$ and $cd$ are distinct edges of G, though possibly adjacent, and no $ac$, $bc$, $ad$ or $bd$path is a chording path of $G\{ab,cd\}$; or
$S=\{x,y,z\}$, where x, y, and z are distinct vertices of G and no $xy$, $xz$ or $yz$path is a chording path of G. Please note that if G is 3connected, then x, y, and z must be pairwise nonadjacent if $\{x,y,z\}$ is 3compatible.
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 3connected graph, then the result is minimally 3connected if and only if the operation is applied to a 3compatible set [
8].
Theorem 5 (Dawes, 1986a)
. Let H be a minimally 3connected 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 3connected if and only if S is a 3compatible set in H.
Dawes also proved that, with the exception of ${W}_{3}$, every minimally 3connected graph can be obtained by applying D1, D2, or D3 to a 3compatible set in a smaller minimally 3connected graph.
Theorem 6 (Dawes, 1986b)
. Let G be a simple graph such that $G\ncong {W}_{3}$. Then G is minimally 3connected if and only if there exists a minimally 3connected graph ${G}^{\prime}$, $E\left({G}^{\prime}\right)<E\left(G\right)$ such that G can be constructed by applying one of D1, D2, or D3 to a 3compatible set in ${G}^{\prime}$.
The next result is the Strong Splitter Theorem [
9]. The rank of a graph, denoted by
$r\left(G\right)$, is the size of a spanning tree. If
G has
n vertices, then
$r\left(G\right)=n1$.
Theorem 7. Suppose G and H are simple 3connected graphs such that G has a proper Hminor, G is not a wheel, and $H\ncong {W}_{3}$. Let $j=r\left(G\right)r\left(H\right)$. Then there is a sequence of 3connected graphs ${G}_{0},{G}_{1},\dots ,{G}_{t}$ such that ${G}_{0}\cong H$, ${G}_{t}=G$, and ${G}_{i1}$ is a minor of ${G}_{i}$ such that:
 (i)
For $1\le i\le j$, $r\left({G}_{i}\right)r\left({G}_{i1}\right)=1$ and $E\left({G}_{i}\right)E\left({G}_{i1}\right)\le 3$; and
 (ii)
For $j<i\le t$, $r\left({G}_{i}\right)=r\left(G\right)$ and $E\left({G}_{i}\right)E\left({G}_{i1}\right)=1$.
Moreover, when $E\left({G}_{i}\right)E\left({G}_{i1}\right)=3$, for $1\le i\le j$, $E\left({G}_{i}\right)E\left({G}_{i1}\right)$ is a triad of ${G}_{i}$.
Our goal is to generate all minimally 3connected 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 3compatibility. The process needs to be correct, in that it only generates minimally 3connected graphs, exhaustive, in that it generates all minimally 3connected graphs, and isomorphfree, 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 3compatible 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 3connected 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 3connected graphs with the exception of two infinite families,
${W}_{n1}$ and
${K}_{3,n3}$, 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 3connected 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 3connected graph, the result is minimally 3connected if and only if S is 3compatible. To check whether a set is 3compatible, 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 NPcomplete 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 3connected 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 edge $ab$ in G to create a new edge $xy$ can be expressed as $(G+e)\circ f$, where $e=xa$ and $f=ay$;
 (b)
D2 applied to two edges $ab$ and $cd$ in G to create a new edge $xy$ can be expressed as $(G+e)\circ \{{f}_{c},{f}_{b}\}$, where $e=bc$, ${f}_{b}=xb$ and ${f}_{c}=cy$; and
 (c)
D3 applied to vertices x, y and z in G to create a new vertex w and edges $xw$, $yw$ and $zw$ can be expressed as $(G+\{{e}_{1},{e}_{2}\})\circ f$, where ${e}_{1}=yx$, ${e}_{2}=zx$ and $f=xw$.
Proof. Operation D1 requires a vertex
x and a nonincident edge
$ab$. The operation is performed by subdividing edge
$ab$ by vertex
y, and adding edge
$xy$. We may also interpret this operation as adding an edge
$e=xa$, and then splitting vertex
a in such a way that
y is the new vertex adjacent to
x and
b, and the new edge
$f=ya$, as shown in
Figure 6. In the process, edge
$e=xa$ is replaced with a new edge
${e}^{\prime}=xy$ and edge
$ab$ is replaced with a new edge
$yb$. Following this interpretation, the resulting graph is
$(G+e)\circ f$.
Operation D2 requires two distinct edges
$ab$ and
$cd$, 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 edge $e=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 ${f}_{c}=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 ${f}_{b}=bx$.
In step (ii), edge $e=bc$ is replaced with a new edge ${e}^{\prime}=yb$ and edge $cd$ is replaced with a new edge $yd$. In step (iii), edge ${e}^{\prime}=yb$ is replaced with a new edge ${e}^{\u2033}=xy$ and $ab$ is replaced with a new edge $xa$. Following this interpretation, the resulting graph is $(G+e)\circ \{{f}_{c},{f}_{b}\}$.
Operation D3 requires three vertices
x,
y, and
z. The operation is performed by adding a new vertex
w and edges
$xw$,
$yw$, and
$zw$. We may interpret this operation as adding one edge
${e}_{1}=xy$, adding a second edge
${e}_{2}=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 edge
$f=xw$. This is illustrated in
Figure 8. Following this interpretation, the resulting graph is
$(G+\{{e}_{1},{e}_{2}\})\circ 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 in $G\backslash K$, and False otherwise. To efficiently determine whether S is 3compatible, 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 of $G\backslash 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}^{\prime}$ obtained from a graph G by:
Adding an edge $uv$ betweeen two nonadjacent vertices u and v; and
Splitting a vertex v in G to form a new vertex ${v}^{\prime}$ of degree 3 that is incident to the new edge $f=v{v}^{\prime}$ and two other edges.
The first lemma shows how the set of cycles can be propagated when an edge $uv$ is added betweeen two nonadjacent vertices u and v.
Lemma 1 (Cycle Chording Lemma)
. Let G be a simple 2connected graph with n vertices and let $\mathcal{C}\left(G\right)$ be the set of cycles of G. Let ${G}^{\prime}$ be obtained from G by adding an edge $uv$ between two nonadjacent vertices in G. Then the cycles of ${G}^{\prime}$ consists of:
 (i)
$\mathcal{C}\left(G\right)$; and
 (ii)
Cyclesandwhereis a cycle in G passing through u and v, as shown in Figure 9.
The complexity of determining the cycles of ${G}^{\prime}$ from the cycles of G is $\mathcal{O}\left(\right\mathcal{C}\left(G\right)\leftn\right)$.
Proof. We need only show that any cycle in ${G}^{\prime}$ can be produced by (i) or (ii). Suppose C is a cycle in ${G}^{\prime}$. If C does not contain the edge $uv$ then C must also be a cycle in G. Otherwise, the edges in C other than $uv$ form a $uv$ path ${P}_{1}$ in G. Since G is 2connected, there is another edgedisjoint $uv$ path ${P}_{2}$ in G. Paths ${P}_{1}$ and ${P}_{2}$ together 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}^{\prime}$ from the cycles of G is $\mathcal{O}\left(\right\mathcal{C}\left(G\right)\leftn\right)$ 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 2connected. It is easy to find a counterexample when G is not 2connected; 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}^{\prime}$ of degree 3 that is incident to the new edge $f=v{v}^{\prime}$ 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}^{\prime}$.
Remove the edge $qv$ and replace it with a new edge $q{v}^{\prime}$.
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 of
$G\circ f$, where
$G\circ f$ is obtained by splitting vertex
v to form a new vertex
${v}^{\prime}$ of degree 3 that is incident to the new edge
$f=v{v}^{\prime}$ 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 edge
$pv$ replaced with the two edges
$p{v}^{\prime}$ and
${v}^{\prime}v$. Cycles without the edge
$pv$ remain 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 where
$ab$ and
$bc$ are edges, but
$ac$ is not an edge. Let
${G}^{\prime}$ be the graph formed from
G by deleting edge
$ab$ and adding edge
$ac$. Think of this as “flipping” the edge
$ab$ to the edge
$ac$ as shown in
Figure 11. Please note that in
Figure 10, this corresponds to removing the edge
$qv$ and replacing it with edge
$q{v}^{\prime}$.
Let
C be any cycle in
G represented by its vertices in order. We may identify cases for determining how individual cycles are changed when
$ab$ is replaced with
$ac$, 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:
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, let $a=1$, $b=4$, and $c=3$. If none of $a,b,c$ appear in C, then there is nothing to do since it remains a cycle in ${G}^{\prime}$.
Rotate the list so that a appears first, if it occurs in the cycle, or b if it appears, or c if it appears: $1\phantom{\rule{0.166667em}{0ex}}5\phantom{\rule{0.166667em}{0ex}}4\phantom{\rule{0.166667em}{0ex}}3\phantom{\rule{0.166667em}{0ex}}0$.
Replace the vertex numbers associated with a, b and c with “a”, “b” and “c”, respectively: $a\phantom{\rule{0.166667em}{0ex}}5\phantom{\rule{0.166667em}{0ex}}b\phantom{\rule{0.166667em}{0ex}}c\phantom{\rule{0.166667em}{0ex}}0$.
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\diamond b\phantom{\rule{0.166667em}{0ex}}c\phantom{\rule{0.166667em}{0ex}}\u25b5$.
It helps to think of these steps as symbolic operations:
15430
$a5bc0$
$a\diamond bc\u25b5$
There is no square in the above example. If we start with cycle 012543 with $a=1$, $b=5$, $c=3$ we get
125430
$a2b4c0$
$a\diamond b\u25b5c\square $
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 casechecking 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 let $\mathcal{C}\left(G\right)$ be the set of cycles of G. Let $a,b,c\in V\left(G\right)$ such that $ab,bc\in E\left(G\right)$, but $ac\notin E\left(G\right)$. Let ${G}^{\prime}$ be the graph obtained from G by replacing $ab$ with a new edge $ac$. The complexity of determining the cycles of ${G}^{\prime}$ is $\mathcal{O}\left(\right\mathcal{C}\left(G\right){}^{2}n)$.
Proof. The cycles of ${G}^{\prime}$ 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}^{\prime}$. 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 from $ab$ to $ac$ based 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$, $abc$ and $acb$, 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}^{\prime}$.
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\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$,
$ab\diamond $, and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5$. Of these
$ab$ is 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\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$: If there is a cycle of the form $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$ in G as shown in the lefthand side of the diagram, then when the flip is implemented and $ab$ is replaced with $ac$ in ${G}^{\prime}$, $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc$ must be a cycle. In other words ${G}^{\prime}$ has a cycle $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc$ in place of cycle $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$. (Cycles in the diagram are indicated with dashed lines.)  
$ab\diamond $: If there is a cycle of the form $ab\diamond $ in G, then ${G}^{\prime}$ has a cycle $acb\diamond $, which is $ab\diamond $ with $ab$ replaced with $acb$.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5$: This cycle remains a cycle in ${G}^{\prime}$.  
Case 2:$ac$: The possible patterns containing
a and
c are
$ac$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$,
$ac\diamond $, and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$. In this case, 3 of the 4 patterns are impossible:
$ac$ is impossible because
G has no parallel edges;
$ac\diamond $ and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$ are impossible because
a and
c are not adjacent. Cycles matching the remaining pattern are propagated as follows:
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$: ${G}^{\prime}$ has the same cycle as G. Two new cycles emerge also, namely $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$ and $ac\diamond $, because $ac$ chords the cycle.  
Case 3:$bc$: The possible patterns containing
b and
c are
$bc$,
$b\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$,
$bc\diamond $, and
$b\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$. In this case,
$bc$ is impossible because
G has no parallel edges. Cycles matching the other three patterns are propagated with no change:
$b\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$: This remains a cycle in ${G}^{\prime}$.  
$bc\diamond $: This remains a cycle in ${G}^{\prime}$.  
$b\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$: This remains a cycle in ${G}^{\prime}$.  
Case 4:$abc$: The eight possible patterns containing
a,
b, and
c in order are
$abc$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc$,
$ab\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5c$,
$abc\diamond $,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc\u25b5$,
$ab\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$, and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5c\square $. In this case, four patterns,
$abc$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc$,
$ab\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$, and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5c$ are all impossible because
a and
c are not adjacent in
G. Cycles matching the other four patterns are propagated as follows:
$abc\diamond $: If G has a cycle of the form $abc\diamond $, then ${G}^{\prime}$ has a cycle $ac\diamond $, which is $abc\diamond $ with $abc$ replaced with $ac$.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}bc\u25b5$: This remains a cycle in ${G}^{\prime}$.  
$ab\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$: If G has a cycle of the form $ab\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5$, then it will be replaced in ${G}^{\prime}$ with two cycles: $b\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$ and $ac\u25b5$.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5c\square $: This remains a cycle in ${G}^{\prime}$.  
Case 5:$acb$: The eight possible patterns containing
a,
c, and
b in order are
$acb$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}cb$,
$ac\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5b$,
$acb\diamond $,
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}cb\u25b5$,
$ac\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5$, and
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5b\square $. In this case, four patterns,
$acb$,
$ac\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b$,
$acb\diamond $, and
$ac\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5$ are impossible because
a and
c are not adjacent in
G. Cycles matching the other four patterns are propagated as follows:
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}cb$: If G has a cycle of the form $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}cb$, then ${G}^{\prime}$ will have a cycle of the form $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c$, which is the original cycle with $cba$ replaced with $ca$.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5b$: If G has a cycle of the form $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5b$, then ${G}^{\prime}$ will have cycles of the form $b\u25b5c$ and $a\diamond c$ in its place.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}cb\u25b5$: This remains a cycle in ${G}^{\prime}$.  
$a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}c\u25b5b\square $: This remains a cycle in ${G}^{\prime}$.  
Case 6: There is one additional case in which two cycles in
G result in one cycle in
${G}^{\prime}$ after the flip operation:
Two cycles in G which share the common vertex b, share no other common vertices and for which the edge $ab$ lies in one cycle and the edge $bc$ lies in the other; that is a pair of cycles with patterns $ab\diamond $ and $b\u25b5c$, correspond to one cycle in ${G}^{\prime}$ of the form $a\phantom{\rule{0.166667em}{0ex}}\diamond \phantom{\rule{0.166667em}{0ex}}b\u25b5c$.  
In all but the last case, an existing cycle has to be traversed to produce a new cycle making it an $\mathcal{O}\left(n\right)$ operation because a cycle may contain at most n vertices. Without the last case, because each cycle has to be traversed the complexity would be $\mathcal{O}\left(\right\mathcal{C}\left(G\right)\leftn\right)$. The last case requires consideration of every pair of cycles which is $\mathcal{O}\left(\right\mathcal{C}\left(G\right){}^{2}n)$. □
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}^{\prime}$ be a simple graph obtained from a smaller 3connected 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}^{\prime}$ can be obtained from the cycles of G by a method with complexity $\mathcal{O}\left({c}^{2}n\right)$.
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 are $\mathcal{O}\left(cn\right)$, $\mathcal{O}\left(c\right)$, and $\mathcal{O}\left({c}^{2}n\right)$, respectively, so the overall complexity is $\mathcal{O}\left({c}^{2}n\right)$. 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 also $\mathcal{O}\left({c}^{2}n\right)$. □
5. IsomorphFree 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 vertex $x\in V\left(G\right)$ and an edge $ab\in E\left(G\right)$ as input, and produces a graph ${G}^{\prime}=(G+e)\circ {f}_{c}$ with $n+1$ vertices and $m+2$ edges (see Theorem 8 (i));
D2 takes a graph G with n vertices and m edges, and two edges $ab,cd\in E\left(G\right)$ as input, and produces a graph ${G}^{\prime}=(G+e)\circ \{{f}_{c},{f}_{b}\}$ with $n+2$ vertices and $m+3$ edges (see Theorem 8 (ii)); and
D3 takes a graph G with n vertices and m edges, and three vertices $x,y,z\in V\left(G\right)$ as input, and produces a graph ${G}^{\prime}=(G+\{{e}_{1},{e}_{2}\})\circ f$ with $n+1$ vertices and $m+3$ edges (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
$\varphi $ produces a data artifact from a graph in such a way that
$\varphi \left({G}_{1}\right)=\varphi \left({G}_{2}\right)$ if and only if
${G}_{1}\cong {G}_{2}$. 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 3connected 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 3connected 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 form $G+{e}_{1}$, where G has n vertices and $m1$ edges, and graphs of the form $(G+{e}_{1})\circ f$, where G has $n1$ vertices and $m2$ edges.
For operation D2, the set may include graphs of the form $G+{e}_{1}$, where G has n vertices and $m1$ edges, graphs of the form $(G+{e}_{1})\circ f$, where G has $n1$ vertices and $m2$ edges, and graphs of the form $(G+{e}_{1})\circ \{{f}_{c},{f}_{b}\}$, where G has $n2$ vertices and $m3$ edges.
For operation D3, the set may include graphs of the form $G+{e}_{1}$ where G has n vertices and $m1$ edges, graphs of the form $G+\{{e}_{1},{e}_{2}\}$, where G has n vertices and $m2$ edges, and graphs of the form $(G+\{{e}_{1},{e}_{2}\})\circ f$, where G has $n1$ vertices and $m3$ edges.
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 IsomorphFree
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 an $m,n$ combination, we define sets ${A}_{m,n}^{(*)}$, where * represents 0, 1, 2, or 3, ${B}_{m,n}$ and ${C}_{m,n}$ as follows:
${A}_{m,n}^{\left(0\right)}$ only ever contains of the “root” graph; i.e., the prism graph. So for values of m and n other than 9 and 6, ${A}_{m,n}^{\left(0\right)}=\u2300$. All graphs in ${A}_{m,n}^{\left(0\right)}$, ${A}_{m,n}^{\left(1\right)}$, ${A}_{m,n}^{\left(2\right)}$, and ${A}_{m,n}^{\left(3\right)}$ are minimally 3connected.
${B}_{m,n}$ consists of graphs generated by adding an edge to a minimally 3connected graph with $m1$ vertices and n edges.
${C}_{m,n}$ consists of graphs generated by adding an edge to a graph in ${B}_{m1,n}$ that is incident with the edge added to form the input graph.
${A}_{m,n}^{\left(1\right)}$ consists of graphs generated by splitting a vertex in a graph in ${B}_{m1,n1}$ that is incident to the edge added to form the input graph, after checking for 3compatibility.
${A}_{m,n}^{\left(2\right)}$ consists of graphs generated by splitting a vertex in a graph in ${A}_{m1,n1}^{\left(1\right)}$ that is incident to the same edge as the vertex split to form the input graph, after checking for 3compatibility.
${A}_{m,n}^{\left(3\right)}$ consists of graphs generated by splitting a vertex in a graph in ${C}_{m1,n1}$ that is incident to the two edges added to form the input graph, after checking for 3compatibility.
Then, beginning with $m=10$ and $n=6$, we construct graphs in ${C}_{m,n}$, ${B}_{m,n}$, ${A}_{m,n}^{\left(1\right)}$, ${A}_{m,n}^{\left(2\right)}$ and ${A}_{m,n}^{\left(3\right)}$, in that order, from input graphs with $m1$ vertices and n edges, and with $m1$ vertices and $n1$ 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 nonisomorphic. 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 with
$m=n+4$ and proceed until no more graphs or generated or, when
$n\ge 8$, when
$m=3n7$. By Theorem 3, no further minimally 3connected graphs will be found after
$m=3n9$ when
$n\ge 8$; however we still need to generate single and doubleedge additions to be used when considering graphs with
$n+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 righthand box, are generated from graphs with
n vertices and
$m1$ edges in the upper lefthand box, and graphs with
$n1$ vertices and
$m1$ edges in the lower lefthand 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)\circ {f}_{c}$,
$(G+e)\circ \{{f}_{c},{f}_{b}\}$, and
$(G+\{{e}_{1},{e}_{2}\})\circ 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 ${A}_{m1,n}^{(*)}$, which are minimally 3connected, to generate all possible single edge additions $G+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 ${B}_{m,n}$.
Procedure E2 is applied to graphs in ${B}_{m1,n}$ and treats an input graph as $G+{e}_{1}$ 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 graph $G+\{{e}_{1},{e}_{2}\}$. 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 ${C}_{m,n}$.
Procedure C1 is applied to graphs in ${B}_{m1,n1}$ and treats an input graph as $G+e$ as defined in operations D1 and D2, as expressed in Theorem 8. It generates two splits $(G+e)\circ 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 ${A}_{m,n}^{\left(1\right)}$. This procedure only produces splits for graphs for which the original set of vertices and edges is 3compatible, and as a result it yields only minimally 3connected graphs.
Procedure C2 is applied to graphs in ${A}_{m1,n1}^{\left(1\right)}$ and treats an input graph as $(G+e)\circ {f}_{c}$ as defined in operation D2, as expressed in Theorem 8. It generates splits $(G+e)\circ \{{f}_{c},{f}_{b}\}$ of the remaining unsplit 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 ${A}_{m,n}^{\left(2\right)}$. This procedure only produces splits for 3compatible input sets, and as a result it yields only minimally 3connected graphs.
Procedure C3 is applied to graphs in ${C}_{m1,n1}$ and treats an input graph as $G+\{{e}_{1},{e}_{2}\}$ as defined in operation D3 as expressed in Theorem 8. For each input graph, it generates one vertex split $(G+\{{e}_{1},{e}_{2}\})\circ 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 ${A}_{m,n}^{\left(3\right)}$. This procedure only produces splits for 3compatible input sets, and as a result it yields only minimally 3connected graphs.
While C1, C2, and C3 produce only minimally 3connected 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 nonisomorphic sets of minimally 3connected 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}^{\prime}$ 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 is $\mathcal{O}\left({n}^{2}\right)$ because the set of edges of G must be copied to form the set of edges of ${G}^{\prime}$.
SplitVertex($G,v,u,w$)—Given a graph G, a vertex v and two edges $vu$ and $vw$, this procedure returns a graph ${G}^{\prime}$ formed from G by adding a vertex ${v}^{\prime}$, adding an edge connecting v and ${v}^{\prime}$, and replacing the edges $vu$ and $vw$ with edges ${v}^{\prime}u$ and ${v}^{\prime}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 is $\mathcal{O}\left({n}^{2}\right)$, again because a copy of the graph must be produced.
NoChordingPaths(
$\mathcal{C},G,P,X$)—Given the set
$\mathcal{C}$ of 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 in
$G\backslash X$. Its complexity is
$\mathcal{O}\left(\right\mathcal{C}\left{n}^{3}\right)$, as it requires all simple paths between two vertices to be enumerated, which is
$\mathcal{O}\left({n}^{2}\right)$. 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 worstcase complexity for any individual procedure in this process is the complexity of C2: $\mathcal{O}\left(\right\mathcal{C}{}^{2}{n}^{3})$.
Procedure
E1 is responsible for implementing the first step of operations D1, D2, and D3. It generates all singleedge additions of an input graph
G, using
ApplyAddEdge to propagate the list of cycles. Its complexity is
$\mathcal{O}\left(\right\mathcal{C}\left{n}^{3}\right)$, as it requires each pair of vertices of
G to be checked, and for each nonadjacent pair
ApplyAddEdge is used to propagate cycles. Pseudocode is shown in Algorithm 3.
Algorithm 3 First edge addition procedure 
1: procedure E1 (G, $\mathcal{C}$) 
2: $S\leftarrow \varphi $ 
3: for $u\in V\left(G\right)$ do 
4: for $v\in V\left(G\right)\backslash u$ do 
5: if $uv\notin E\left(G\right)$ then 
6: ${G}^{\prime}\leftarrow $ AddEdge $(G,u,v)$ 
7: ${\mathcal{C}}^{\prime}\leftarrow $ ApplyAddEdge$(\mathcal{C},u,v)$ 
8: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime},uv)\right\}$ 
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 singleedge additions of an input graph, but under a certain condition. Specifically, given an input graph
$G=H+{e}_{1}$ with cycles
$\mathcal{C}$, as produced by
E1,
E2 produces all graphs
$H+\{{e}_{1},{e}_{2}\}$, where the new edge
${e}_{2}$ is adjacent to
${e}_{1}$. Its complexity is
$\mathcal{O}\left(\right\mathcal{C}\left{n}^{2}\right)$, 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, $\mathcal{C}$) 
2: $S\leftarrow \varphi $ 
3: for $w\in V\left(G\right)$ do 
4: if $wu\notin E\left(G\right)$ then 
5: ${G}^{\prime}\leftarrow $ AddEdge$(G,u,w)$ 
6: ${\mathcal{C}}^{\prime}\leftarrow $ ApplyAddEdge$(\mathcal{C},u,w)$ 
7: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime},uw)\right\}$ 
8: end if 
9: if $wv\notin E\left(G\right)$ then 
10: ${G}^{\prime}\leftarrow $ AddEdge$(G,w,v)$ 
11: ${\mathcal{C}}^{\prime}\leftarrow $ ApplyAddEdge$(\mathcal{C},w,v)$ 
12: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime},wv)\right\}$ 
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 graph
$G=H+e$ generated by
E1; let
$bc$ denote the added edge. Observe that the chording path checks are made in
H, which is
$G\backslash bc$.
First, for any vertex
$a\in N\left(b\right)\backslash c$ in
G, where there are no chording
$ca$ or
$bc$ paths in
$G\backslash \{bc,ba\}=H\backslash 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 vertex
$d\in N\left(c\right)\backslash b$ in
G where there are no chording
$bd$ or
$bc$ paths in
$G\backslash \{bc,cd\}=H\backslash 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 make
$\mathcal{O}\left(n\right)$ calls to
ApplyFlipEdge, where
$n=\leftV\right(G\left)\right$, its complexity is
$\mathcal{O}\left(\right\mathcal{C}{}^{2}{n}^{2})$. Pseudocode is shown in Algorithm 5.
Algorithm 5 First vertex split procedure 
1: procedureC1(G, b, c, $\mathcal{C}$) 
2: $S\leftarrow \varphi $ 
3: for $a\in N\left(b\right)\backslash c$ do ▹ Split b 
4: if NoChordingPaths$(\mathcal{C},G,\{(c,a),(b,c)\},\{bc,ba\left\}\right)$ then 
5: ${G}^{\prime},x\leftarrow $ SplitVertex $(G,b,c,a)$ 
6: ${\mathcal{C}}^{\prime}\leftarrow $ ApplySubdivideEdge $(\mathcal{C},b,c,x)$ 
7: ${\mathcal{C}}^{\prime}\leftarrow $ ApplyFlipEdge $({\mathcal{C}}^{\prime},a,b,x)$ 
8: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime},b,c,a,x)\right\}$ 
9: end if 
10: end for 
11: for $d\in N\left(c\right)\backslash b$ do ▹ Split c 
12: if NoChordingPaths$(\mathcal{C},G,\{(b,d),(c,b)\},\{bc,cd\left\}\right)$ then 
13: ${G}^{\prime},y\leftarrow $ SplitVertex $(G,c,b,d)$ 
14: ${\mathcal{C}}^{\prime}\leftarrow $ ApplySubdivideEdge $(\mathcal{C},c,b,y)$ 
15: ${\mathcal{C}}^{\prime}\leftarrow $ ApplyFlipEdge $({\mathcal{C}}^{\prime},d,c,y)$ 
16: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime},c,b,d,y)\right\}$ 
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 graph
$G=(H+e)\circ f$ generated by
C1; we denote
${e}^{\prime}$ and
f shown in the figure as
$yb$ and
$yc$, 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 no
$ca$,
$cb$,
$db$, or
$da$ chording paths in
$G\backslash \{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 no $ka$ or $kb$ chording paths in $G\backslash \{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 make
$\mathcal{O}\left({n}^{2}\right)$ calls to
ApplyFlipEdge, where
$n=\leftV\right(G\left)\right$, its complexity is
$\mathcal{O}\left(\right\mathcal{C}{}^{2}{n}^{3})$. Pseudocode is shown in Algorithm 6.
Algorithm 6 Second vertex split procedure 
1: procedure C2($G,\mathcal{C},c,b,d,y$) 
2: $S\leftarrow \varphi $ 
3: for $a\in N\left(b\right)\backslash \{c,d,y\}$ do ▹ Final step of Operation (c) 
4: if NoChordingPaths$(\mathcal{C},G,\{(c,a),(c,b),(d,b),(d,a)\},\{ab,by,cy,dy\left\}\right)$ then 
5: ${G}^{\prime},x\leftarrow $ SplitVertex $(G,b,y,a)$ 
6: ${\mathcal{C}}^{\prime}\leftarrow $ ApplySubdivideEdge $(\mathcal{C},b,a,x)$ 
7: ${\mathcal{C}}^{\u2033}\leftarrow $ ApplyFlipEdge $({\mathcal{C}}^{\prime},y,b,x)$ 
8: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\u2033})\right\}$ 
9: end if 
10: end for 
11: for $a,k\in N\left(b\right)\backslash \{c,d,y\}$ do ▹ Final step of Operation (d) 
12: if NoChordingPaths$(\mathcal{C},G,\{(k,a),(k,b)\},\{ab,by,cy,dy\left\}\right)$ then 
13: ${G}^{\prime},x\leftarrow $ SplitVertex $(G,b,k,a)$ 
14: ${\mathcal{C}}^{\prime}\leftarrow $ ApplySubdivideEdge $(\mathcal{C},b,a,x)$ 
15: ${\mathcal{C}}^{\u2033}\leftarrow $ ApplyFlipEdge $({\mathcal{C}}^{\prime},k,b,x)$ 
16: $S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\u2033})\right\}$ 
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 graph
$G=H+\{{e}_{1},{e}_{2}\}$ generated by
E2, where
${e}_{1}=xy$ and
${e}_{2}=xz$ are 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 no
$xy$,
$xz$, or
$yz$ chording paths in
$G\backslash \{xy,xz\}=H$. Because
C3 makes one call to
ApplyFlipEdge, its complexity is
$\mathcal{O}\left(\right\mathcal{C}{}^{2}n)$. Pseudocode is shown in Algorithm 7.
Algorithm 7 Third vertex split procedure 
 1:
procedureC3($G,\mathcal{C},x,y,z$)  2:
$S\leftarrow \varphi $  3:
if NoChordingPaths$(\mathcal{C},G,\{(x,y),(x,z),(y,z)\},\{xy,xz\left\}\right)$ then  4:
${G}^{\prime},w\leftarrow $ SplitVertex $(G,x,y,z)$  5:
${\mathcal{C}}^{\prime}\leftarrow $ ApplySubdivideEdge $(\mathcal{C},x,z,w)$  6:
${\mathcal{C}}^{\prime}\leftarrow $ ApplyFlipEdge( $({\mathcal{C}}^{\prime},y,x,w)$  7:
$S\leftarrow S\cup \left\{({G}^{\prime},{\mathcal{C}}^{\prime})\right\}$  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 3connected graph and ${G}^{\prime}$ is obtained from G by applying one of the operations D1, D2, and D3 to a set S of vertices and edges, then ${G}^{\prime}$ is minimally 3connected if and only if S is 3compatible, and also that any minimally 3connected graph other than ${W}_{3}$ can be obtained from a smaller minimally 3connected graph by applying D1, D2, or D3 to a 3compatible set. This shows that application of these operations to 3compatible sets of edges and vertices in minimally 3connected graphs, starting with ${W}_{3}$, 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
${W}_{3}$ itself, as shown in
Figure 16. Observe that
$\{x,ab\}$ is a 3compatible set because there are clearly no chording
$xa$ or
$xb$paths in
${W}_{3}\backslash ab$, so we may apply D1 to produce another minimally 3connected graph, which is actually
${W}_{4}$ as shown in the figure. However, since there are already edges
$xa$ and
$xb$ in the graph, if we are to apply our stepbystep 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
${W}_{3}$. We are now ready to prove the third main result in this paper.
Theorem 10. Let G be a simple minimally 3connected graph. Then one of the following statements is true:
 1.
$G\cong {W}_{n1}$ for $n\ge 5$ and G can be obtained from ${W}_{n2}$ by applying operation D1 to the spoke vertex x and a rim edge $ab$;
 2.
$G\cong {K}_{3,n3}$ for $n\ge 7$ and G can be obtained from ${K}_{3,n4}$ by applying operation D3 to the 3 vertices in the smaller class; or
 3.
G has a prism minor, for $n\ge 7$, and G can be obtained from a smaller minimally 3connected graph ${G}^{\prime}$ with a prism minor, where $\leftE\left(G\right)\rightE\left({G}^{\prime}\right)\le 3$, using operation D1, D2, or D3.
Proof. Theorem 2 characterizes the 3connected graphs without a prism minor. Of these, the only minimally 3connected ones are ${W}_{n1}$ for $n\ge 4$ and ${K}_{3,n3}$ for $n\ge 6$. Observe that for $n\ge 5$, ${W}_{n1}\backslash e/f={W}_{n2}$, where e is a spoke and f is a rim edge, such that $e,f$ are incident to a degree 3 vertex. Therefore ${W}_{n1}$ can be obtained from ${W}_{n2}$ by applying operation D1 to the spoke vertex x and a rim edge $ab$. The set $\{x,ab\}$ is 3compatible because any chording edge of a cycle in ${W}_{n2}\backslash ab$ would have to be a spoke edge, and since all rim edges have degree three the chording edge cannot be extended into a $xa$ or $xb$path.
Observe that, for
$n\ge 7$,
${K}_{3,n3}w={K}_{3,n4}$, where
w is a degree 3 vertex. Therefore,
${K}_{3,n3}$ can be obtained from a smaller minimally 3connected graph of the same family by applying operation D3 to the three vertices in the smaller class. The set of three vertices is 3compatible 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 3connected graph with $n1$ vertices and $m1$ edges via an edge addition and a vertex split, from a graph with $n2$ vertices and $m3$ edges via two edge additions and a vertex split, or from a graph with $n1$ vertices and $m3$ edges 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 3connected graphs can be obtained from smaller minimally 3connected graphs by applying these operations to 3compatible sets. □
We constructed all nonisomorphic minimally 3connected graphs up to 12 vertices using a Python implementation of these procedures. The total number of minimally 3connected 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 nonisomorphic 3connected 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 to
$n=14$. We were able to obtain the set of 3connected cubic graphs up to 20 vertices as shown in
Table 2.
All of the minimally 3connected 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 3connected and that all single edgedeletions of the graph were not. The overall number of generated graphs was checked against the published sequence on OEIS.
The 3connected cubic graphs were verified to be 3connected using a similar procedure, and overall numbers for up to 14 vertices were checked against the published sequence on OEIS.
The minimally 3connected graphs were generated in 31 h on a PC with an Intel Core I54460 CPU at 3.2 GHz and 16 Gb of RAM. The 3connected 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 worstcase 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.