# Constructing Minimally 3-Connected Graphs
## 2 Terminology, Previous Results, and Outline of the Paper
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 [PERSON]'s characterization of 3-connected graphs without a prism minor ([PERSON], 1961). The graphs \(K^{\prime}_{3,n-3}\), \(K^{\prime\prime}_{3,n-3}\), and \(K^{\prime\prime\prime}_{3,n-3}\) are obtained from the complete bipartite graph \(K_{3,n-3}\) (shown in Figure 1) with one, two, or three edges, respectively, joining the three vertices in one class. Theorem 2 ([PERSON], 1963): _A simple \(3\)-connected graph \(G\) has no prism-minor if and only if \(G\) is isomorphic to \(K_{5}\backslash e\), \(K_{5}\), \(W_{n-1}\), for \(n\geq 4\), \(K_{3,n-3}\), \(K^{\prime}_{3,n-3}\), \(K^{\prime\prime}_{3,n-3}\), or \(K^{\prime\prime\prime}_{3,n-3}\), for \(n\geq 6\)._  
Theorem 2 implies that there are only two infinite families of minimally 3-connected graphs without a prism-minor, namely \(W_{n-1}\) for \(n\geq 4\) and \(K_{3,n-3}\) for \(n\geq 6\). Thus, we may focus on constructing minimally 3-connected graphs with a prism minor. Next, [PERSON] 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 ([PERSON], 1961). Theorem 3 ([PERSON], 1969): _Let \(G\) be a minimally \(3\)-connected graph on \(n\geq 8\) vertices. Then \(|E(G)|\leq 3n-9\). Moreover, \(|E(G)|=3n-9\) if and only if \(G\cong K_{3,n-3}\)._  
In 1969 [PERSON] and [PERSON] defined two operations based on subdivisions and gave an alternative construction theorem for 3-connected graphs ([PERSON] and [PERSON], 1961). 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 Grunbaum operation is defined as follows: Subdivide an edge \(ab\) by vertex \(y\) and add edge \(xy\) for a vertex \(x\
eq a,b\). This is what we called \"bridging a vertex and an edge\" in Section 1. The second Barnette and Grunbaum 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 3-connectivity. Theorem 4 ([PERSON], 1961): _Let \(G\) be a simple graph such that \(G\
cong W_{3}\). Then \(G\) is \(3\)-connected 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, [PERSON] gave a necessary and sufficient characterization for the construction of minimally 3-connected graphs starting with \(W_{3}\). He used the two Barnett and Grunbaum 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 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, [PERSON] gave a necessary and sufficient condition for the construction of minimally 3-connected graphs. [PERSON] 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. [PERSON] 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 edge \(e\
ot\in C\) that links two vertices in \(C\).