# Constructing Minimally 3-Connected Graphs
## 3 Results Establishing Correctness of the Algorithm
Moreover, as explained above, in this representation, \(\diamond\), \(\triangle\), and \(\square\) simply represent sequences of vertices in the cycle other than \(a\), \(b\), or \(c\); the sequences they represent could be of any length. Finally, unlike Lemma 1, there are no connectivity conditions on Lemma 2. Lemma 2 (Edge Flip Lemma): _Let \(G\) be a simple graph with \(n\) vertices and let \(\mathcal{C}(G)\) be the set of cycles of \(G\). Let \(a,b,c\in V(G)\) such that \(ab,bc\in E(G)\), but \(ac\
otin E(G)\). Let \(G^{\prime}\) be the graph obtained from \(G\) by replacing \(ab\) with a new edge \(ac\). The complexity of determining the cycles of \(G^{\prime}\) is \(\mathcal{O}(|\mathcal{C}(G)|^{2}n)\)._  
Proof. : The cycles of \(G^{\prime}\) can be determined from the cycles of \(G\) by analysis of patterns as described above. First observe that any cycle in \(G\) that does not include at least two of the vertices \(a\), \(b\), and \(c\) remains a cycle in \(G^{\prime}\). If a cycle of \(G\) does contain at least two of \(a\), \(b\), and \(c\), then we can evaluate how the cycle is affected by the flip from \(ab\) to \(ac\) based on the cycle's pattern. We can enumerate all possible patterns by first listing all possible orderings of at least two of \(a\), \(b\) and \(c\): \(ab\), \(ac\), \(bc\), \(abc\) and \(acb\), and then for each one identifying the possible patterns. Representing cycles in this fashion allows us to distill all of the cycles passing  
Figure 7:5 The prism graph. through at least 2 of \(a\), \(b\) and \(c\) in \(G\) into 6 cases with a total of 16 subcases for determining how they relate to cycles in \(G^{\prime}\). _Case 1: \(ab\)_: A pattern containing \(a\) and \(b\) may or may not include vertices between \(a\) and \(b\), and may or may not include vertices between \(b\) and \(a\). This results in four combinations: \(ab\), \(a\diamond b\), \(ab\diamond\), and \(a\diamond b\triangle\). Of these \(ab\) is impossible because \(G\) has no parallel edges, and therefore a cycle in \(G\) must have three edges. Cycles matching the other three patterns are propagated as follows:  
\(a\diamond b\): If there is a cycle of the form \(a\diamond b\) in \(G\) as shown in the left-hand side of the diagram, then when the flip is implemented and \(ab\) is replaced with \(ac\) in \(G^{\prime}\), \(a\diamond bc\) must be a cycle. In other words \(G^{\prime}\) has a cycle \(a\diamond bc\) in place of cycle \(a\diamond b\). (Cycles in the diagram are indicated with dashed lines.) \(ab\diamond\): If there is a cycle of the form \(ab\diamond\) in \(G\), then \(G^{\prime}\) has a cycle \(acb\diamond\), which is \(ab\diamond\) with \(ab\) replaced with \(acb\). \(a\diamond b\triangle\): This cycle remains a cycle in \(G^{\prime}\). _Case 2: \(ac\)_: The possible patterns containing \(a\) and \(c\) are \(ac\), \(a\diamond c\), \(a\diamond\), and \(a\diamond c\triangle\). In this case, 3 of the 4 patterns are impossible: \(ac\) is impossible because \(G\) has no parallel edges; \(ac\diamond\) and \(a\diamond c\) are impossible because \(a\) and \(c\) are not adjacent. Cycles matching the remaining pattern are propagated as follows:  
\(a\diamond c\triangle\): \(G^{\prime}\) has the same cycle as \(G\). Two new cycles emerge also, namely \(a\diamond c\) and \(ac\diamond\), because \(ac\) chords the cycle. _Case 3: \(bc\)_: The possible patterns containing \(b\) and \(c\) are \(bc\), \(b\diamond c\), \(b\diamond\), and \(b\diamond c\triangle\). In this case, \(bc\) is impossible because \(G\) has no parallel edges. Cycles matching the other three patterns are propagated with no change:  
\(b\diamond c\): This remains a cycle in \(G^{\prime}\). \(b\diamond c\triangle\): This remains a cycle in \(G^{\prime}\). _Case 4: \(abc\)_: The eight possible patterns containing \(a\), \(b\), and \(c\) in order are \(abc\), \(a\diamond bc\), \(ab\diamond c\), \(a\diamond b\triangle c\), \(ab\diamond c\triangle\), \(ab\diamond c\triangle\), and \(a\diamond b\triangle c\square\).