# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm
```
1:procedureC3(\(G,\mathcal{C},x,y,z\))
2:\(S\leftarrow\phi\)
3:ifNoChordingPaths(\(\mathcal{C},G,\{(x,y),(x,z),(y,z)\},\{xy,xz\}\)) then
4:\(G^{\prime},w\leftarrow\textsc{SplitVertex}(G,x,y,z)\)
5:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplySubdivideEdge}(\mathcal{C},x,z,w)\)
6:\(\mathcal{C}^{\prime}\leftarrow\textsc{ApplyFlipEdge}(\mathcal{C}^{



## 6 The Algorithm Is Exhaustive

Theorem 5 and Theorem 6 ([PERSON] results) state that, if \(G\) is a minimally \(3\)-connected 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 \(3\)-connected if and only if \(S\) is \(3\)-compatible, and also that any minimally \(3\)-connected graph other than \(W_{3}\) can 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 \(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 \(3\)-compatible 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 \(3\)-connected 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 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 \(W_{3}\). 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\cong W_{n-1}\) _for_ \(n\geq 5\) _and_ \(G\) _can be obtained from_ \(W_{n-2}\) _by applying operation_ \(D1\) _to the spoke vertex_ \(x\) _and a rim edge ab;_
2. \(G\cong K_{3,n-3}\) _for_ \(n\geq 7\) _and_ \(G\) _can be obtained from_ \(K_{3,n-4}\) _by applying operation_ \(D3\) _to the_ \(3\) _vertices in the smaller class; or_
3. \(G\) _has a prism minor, for_ \(n\geq 7\)_, and_ \(G\) _can be obtained from a smaller minimally_ \(3\)_-connected graph_ \(G^{\prime}\) _with a prism minor, where_ \(|E(G)|-|E(G^{\prime})|\leq 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 \(W_{n-1}\) for \(n\geq 4\) and \(K_{3,n-3}\) for \(n\geq 6\). Observe that for \(n\geq 5\), \(W_{n-1}\backslash e/f=W_{n-2}\), where \(e\) is a spoke and \(f\) is a rim edge, such that \(e,f\) are incident to a degree \(3\) vertex. Therefore \(W_{n-1}\) can be obtained from \(W_{n-2}\) by applying operation D1 to the spoke vertex \(x\) and a rim edge \(ab\). The set \(\{x,ab\}\) is \(3\)-compatible because any chording edge of a cycle in \(W_{n-2}\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. Figure 16: Operation D1 applied to \(W_{3}\). Observe that, for \(n\geq 7\), \(K_{3,n-3}-w=K_{3,n-4}\), where \(w\) is a degree 3 vertex. Therefore, \(K_{3,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.