# Constructing Minimally 3-Connected Graphs
## 3 Results Establishing Correctness of the Algorithm
We may interpret this operation as adding one edge \(e_{1}=xy\), adding a second edge \(e_{2}=xz\), and then splitting the vertex \(x\) in such a way that \(w\) is the new vertex adjacent to \(y\) and \(z\), and the new edge \(f=xw\). This is illustrated in Figure 8. Following this interpretation, the resulting graph is \((G+\{e_{1},e_{2}\})\circ f\). Figure 6: Operation D1 interpreted as an edge addition followed by a vertex split. Figure 7: Operation D2 interpreted as an edge addition followed by two vertex splits. In Theorem 8, it is possible that the initially added edge in each of the sequences above is a parallel edge; however we will see in Section 6 that we can avoid adding parallel edges by selecting our initial \"seed\" graph carefully. Consider the function \(\textsc{HasChordingPath}(G,a,b,K)\), where \(G\) is a graph, \(a\) and \(b\) are vertices in \(G\) and \(K\) is a set of edges, whose value is True if there is a chording path from \(a\) to \(b\) in \(G\setminus K\), and False otherwise. To efficiently determine whether \(S\) is 3-compatible, whether \(S\) is a set consisting of a vertex and an edge, two edges, or three vertices, we need to be able to evaluate HasChordingPath. To evaluate this function, we need to check all paths from \(a\) to \(b\) for chording edges, which in turn requires knowing the cycles of \(G\setminus K\). The second theorem in this section establishes a bound on the complexity of obtaining cycles of a graph from cycles of a smaller graph. The proof consists of two lemmas, interesting in their own right, and a short argument. Using Theorem 8, we can propagate the list of cycles of a graph through operations D1, D2, and D3 if it is possible to determine the cycles of a graph \(G^{\prime}\) obtained from a graph \(G\) by:  
* Adding an edge \(uv\) betweeen two non-adjacent vertices \(u\) and \(v\); and
* Splitting a vertex \(v\) in \(G\) to form a new vertex \(v^{\prime}\) of degree 3 that is incident to the new edge \(f=vv^{\prime}\) and two other edges. The first lemma shows how the set of cycles can be propagated when an edge \(uv\) is added betweeen two non-adjacent vertices \(u\) and \(v\). **Lemma 1** (Cycle Chording Lemma). : _Let \(G\) be a simple 2-connected graph with \(n\) vertices and let \(\mathcal{C}(G)\) be the set of cycles of \(G\). Let \(G^{\prime}\) be obtained from \(G\) by adding an edge \(uv\) between two non-adjacent vertices in \(G\). Then the cycles of \(G^{\prime}\) consists of:_  
1. \(\mathcal{C}(G)\)_; and_
2. _Cycles_ \[w_{1},\ldots,w_{i},u,v,w_{j+1},\ldots,w_{k},w_{1}\] _and_ \[u,w_{i+1},\ldots,w_{j},v,u,\] _where_ \[w_{1},\ldots,w_{i},u,w_{i+1},\ldots,w_{j},v,w_{j+1},\ldots,w_{k},w_{1}\] _is a cycle in_ \(G\) _passing through_ \(u\) _and_ \(v\)_, as shown in Figure_ 9_._ _The complexity of determining the cycles of_ \(G^{\prime}\) _from the cycles of_ \(G\) _is_ \(\mathcal{O}(|\mathcal{C}(G)|n)\)_._  
Figure 8: Operation D3 interpreted as two edge additions followed by a vertex split. Figure 9: Chording a cycle  
Proof. : We need only show that any cycle in \(G^{\prime}\) can be produced by (i) or (ii). Suppose \(C\) is a cycle in \(G^{\prime}\). If \(C\) does not contain the edge \(uv\) then \(C\) must also be a cycle in \(G\). Otherwise, the edges in \(C\) other than \(uv\) form a \(u-v\) path \(P_{1}\) in \(G\). Since \(G\) is 2-connected, there is another edge-disjoint \(u-v\) path \(P_{2}\) in \(G\). Paths \(P_{1}\) and \(P_{2}\) together form a cycle in \(G\), and \(C\) can be obtained from this cycle using the operation in (ii) above. Finally, the complexity of determining the cycles of \(G^{\prime}\) from the cycles of \(G\) is \(\mathcal{O}(|\mathcal{C}(G)|n)\) because each cycle has to be traversed once and the maximum number of vertices in a cycle is \(n\). The graph \(G\) in the statement of Lemma 1 must be 2-connected. It is easy to find a counterexample when \(G\) is not 2-connected; adding an edge to a graph containing a bridge may produce many cycles that are not obtainable from cycles in \(G\) by Lemma 1 (ii).