# Constructing Minimally 3-Connected Graphs
## 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 and \(n-1\) spokes denoted by \(W_{n-1}\) for \(n\geq 4\) and the complete bipartite graph with 3 vertices in one class and \(n-3\) vertices in the other class denoted by \(K_{3,n-3}\) for \(n\geq 6\). See Figure 1.  
[PERSON] 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. Figure 1: The prism graph, \(W_{n-1}\) for \(n\geq 4\), and \(K_{3,n-3}\) for \(n\geq 6\). A cubic graph is a graph whose vertices have degree 3. Let \(G\) and \(H\) be 3-connected cubic graphs such that \(G\
cong 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. [PERSON] 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 edge \(e=uv\) to 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 to \(n=14\). We were able to quickly obtain such graphs up to \(n=20\). [PERSON]'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. [PERSON] gave a necessary and sufficient characterization for the construction of minimally 3-connected 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\
eq 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\). [PERSON] proved that starting with \(W_{3}\) 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 [PERSON] 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 [PERSON] 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 [PERSON] 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  
Figure 3: Bridging two edges and bridging a vertex and an edge. Figure 2: [PERSON]’s vertex split operation. constructing the set of cycles for a graph \(G^{\prime}\) obtained from a graph \(G\) by edge additions and vertex splits, and [PERSON] 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^{\prime}\) can be obtained from the set of cycles of \(G\) by a method with complexity \(\mathcal{O}(c^{2}n)\).