# Constructing Minimally 3-Connected Graphs
## 2 Terminology, Previous Results, and Outline of the Paper
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, [PERSON] 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:  
1. \(S=\{x,ab\}\), where \(x\) is a vertex of \(G\), \(ab\) is an edge of \(G\), \(x\
eq a,b\) and no \(xa\)-path or \(xb\)-path is a chording path of \(G-ab\);
2. \(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
3. \(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 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. [PERSON] 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** ([PERSON], 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\)._  
[PERSON] also proved that, with the exception of \(W_{3}\), 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** ([PERSON], 1986b). : _Let \(G\) be a simple graph such that \(G\
ot\cong W_{3}\). Then \(G\) is minimally 3-connected if and only if there exists a minimally 3-connected graph \(G^{\prime}\), \(|E(G^{\prime})|<|E(G)|\) such that \(G\) can be constructed by applying one of D1, D2, or D3 to a 3-compatible set in \(G^{\prime}\)._  
Figure 4: [PERSON] third operation. Figure 5: A chording path. The next result is the Strong Splitter Theorem [9]. The rank of a graph, denoted by \(r(G)\), is the size of a spanning tree. If \(G\) has \(n\) vertices, then \(r(G)=n-1\). Theorem 3.2: _Suppose \(G\) and \(H\) are simple \(3\)-connected graphs such that \(G\) has a proper \(H\)-minor, \(G\) is not a wheel, and \(H\
ot\
ot\approx W_{3}\). Let \(j=r(G)-r(H)\). Then there is a sequence of \(3\)-connected graphs \(G_{0},G_{1},\ldots,G_{t}\) such that \(G_{0}\cong H\), \(G_{t}=G\), and \(G_{i-1}\) is a minor of \(G_{i}\) such that:_  
_(i)_ _For_ \(1\leq i\leq j\)_,_ \(r(G_{i})-r(G_{i-1})=1\) _and_ \(|E(G_{i})|-|E(G_{i-1})|\leq 3\)_; and_  
_(ii)_ _For_ \(j<i\leq t\)_,_ \(r(G_{i})=r(G)\) _and_ \(|E(G_{i})|-|E(G_{i-1})|=1\)_._  
_Moreover, when \(|E(G_{i})|-|E(G_{i-1})|=3\), for \(1\leq i\leq j\), \(E(G_{i})-E(G_{i-1})\) is a triad of \(G_{i}\)._  
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 3.2, 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.