# Constructing Minimally 3-Connected Graphs
## 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 \(3\)-connected graphs. According to Theorem 3.2, when operation D1, D2, or D3 is applied to a set \(S\) of edges and/or vertices in a minimally \(3\)-connected graph, the result is minimally \(3\)-connected if and only if \(S\) is \(3\)-compatible. To check whether a set is \(3\)-compatible, 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 NP-complete 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 3.2, expresses operations D1, D2, and D3 in terms of edge additions and vertex splits. The second theorem in this section, Theorem 3.2, 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 \(3\)-connected graph. Operations \(D1\), \(D2\), and \(D3\) can be expressed as a sequence of edge additions and vertex splits. Specifically:_  
1. \(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\)_;_
2. \(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_
3. \(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:  
1. Add an edge \(e=bc\);
2. 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
3. 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^{\prime\prime}=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\).