# Constructing Minimally 3-Connected Graphs
## 3 Results Establishing Correctness of the Algorithm
In this case, four patterns, \(abc\), \(a\diamond bc\), \(ab\diamond c\), and \(a\diamond b\triangle c\) are all impossible because \(a\) and \(c\) are not adjacent in \(G\). Cycles matching the other four patterns are propagated as follows:_abc_: If \(G\) has a cycle of the form \(abc\circ\), then \(G^{\prime}\) has a cycle \(ac\circ\), which is \(abc\circ\) with \(abc\) replaced with \(ac\). _a_\(\circ bc\triangle\): This remains a cycle in \(G^{\prime}\). _abc_\(\triangle\): If \(G\) has a cycle of the form \(abc\circ\triangle\), then it will be replaced in \(G^{\prime}\) with two cycles: \(b\circ c\) and \(ac\triangle\). _a_\(\circ b\triangle c\square\): This remains a cycle in \(G^{\prime}\). _Case 5: acb_: The eight possible patterns containing \(a\), \(c\), and \(b\) in order are \(acb\), \(ac\circ\triangle b\), \(acb\), \(acb\), \(acb\), \(acb\triangle\), \(acb\triangle\), and \(ac\circ\triangle b\square\). In this case, four patterns, \(acb\), \(acb\), \(acb\diamond\), and \(ac\circ b\triangle\) are impossible because \(a\) and \(c\) are not adjacent in \(G\). Cycles matching the other four patterns are propagated as follows:  
_a_\(\circ cb\): If \(G\) has a cycle of the form \(a\circ cb\), then \(G^{\prime}\) will have a cycle of the form \(a\circ c\), which is the original cycle with \(cba\) replaced with \(ca\). _a_\(\circ c\triangle b\): If \(G\) has a cycle of the form \(a\circ c\triangle b\), then \(G^{\prime}\) will have cycles of the form \(b\triangle c\) and \(a\circ c\) in its place. _a_\(\circ cb\triangle\): This remains a cycle in \(G^{\prime}\). _a_\(\circ c\triangle b\square\): This remains a cycle in \(G^{\prime}\). _Case 6:_ There is one additional case in which two cycles in \(G\) result in one cycle in \(G^{\prime}\) after the flip operation:  
Two cycles in \(G\) which share the common vertex \(b\), share no other common vertices and for which the edge \(ab\) lies in one cycle and the edge \(bc\) lies in the other; that is a pair of cycles with patterns \(ab\diamond\) and \(b\triangle c\), correspond to one cycle in \(G^{\prime}\) of the form \(a\circ b\triangle c\). In all but the last case, an existing cycle has to be traversed to produce a new cycle making it an \(\mathcal{O}(n)\) operation because a cycle may contain at most \(n\) vertices. Without the last case, because each cycle has to be traversed the complexity would be \(\mathcal{O}(|\mathcal{C}(G)|n)\). The last case requires consideration of every pair of cycles which is \(\mathcal{O}(|\mathcal{C}(G)|^{2}n)\). Now, using Lemmas 1 and 2 we can establish bounds on the complexity of identifyingthe cycles of a graph obtained by one of operations D1, D2, and D3, in terms of the cycles of the original graph. Theorem 4.2: _Let \(G^{\prime}\) be a simple graph obtained from a smaller \(3\)-connected graph \(G\) by one of operations D1, D2, and D3. Let \(n\) be the number of vertices in \(G\) and let \(c\) be the number of cycles of \(G\). Then the cycles of \(G^{\prime}\) can be obtained from the cycles of \(G\) by a method with complexity \(\mathcal{O}(c^{2}n)\)._  
Proof: Using Theorem 4.2, operation D1 can be expressed as an edge addition, followed by an edge subdivision, followed by an edge flip. By Lemmas 1 and 2, the complexities for these individual steps are \(\mathcal{O}(cn)\), \(\mathcal{O}(c)\), and \(\mathcal{O}(c^{2}n)\), respectively, so the overall complexity is \(\mathcal{O}(c^{2}n)\). Similarly, operation D2 can be expressed as an edge addition, followed by two edge subdivisions and edge flips, and operation D3 can be expressed as two edge additions followed by an edge subdivision and an edge flip, so the overall complexity of propagating the list of cycles for D2 and D3 is also \(\mathcal{O}(c^{2}n)\).