# Constructing Minimally 3-Connected Graphs
## 3 Results Establishing Correctness of the Algorithm
Obtaining the cycles when a vertex \(v\) is split to form a new vertex \(v^{\prime}\) of degree 3 that is incident to the new edge \(f=vv^{\prime}\) and two other edges is more complicated. For the purpose of identifying cycles, we regard a vertex split, where the new vertex has degree 3, as a sequence of two \"atomic\" operations. Let \(v\) be a vertex in a graph \(G\) of degree at least 4, and let \(p\), \(q\), \(r\), and \(s\) be four other vertices in \(G\) adjacent to \(v\). The following two steps describe a vertex split of \(v\) in which \(p\) and \(q\) become adjacent to the new vertex and \(r\) and \(s\) remain adjacent to \(v\):  
1. Subdivide the edge joining \(v\) and \(p\), adding a new vertex \(v^{\prime}\). 2. Remove the edge \(qv\) and replace it with a new edge \(qv^{\prime}\). This is illustrated in Figure 7:0 By thinking of the vertex split this way, if we start with the set of cycles of \(G\), we can determine the set of cycles of \(G\circ f\), where \(G\circ f\) is obtained by splitting vertex \(v\) 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 cycles of the graph resulting from step (1) above are simply the cycles of \(G\), with any occurrence of the edge \(pv\) replaced with the two edges \(pv^{\prime}\) and \(v^{\prime}v\). Cycles without the edge \(pv\) remain unchanged. The cycles of the graph resulting from step (2) above are more complicated. Suppose \(G\) is a graph and consider three vertices \(a\), \(b\), and \(c\) in \(G\) where \(ab\) and \(bc\) are edges, but \(ac\) is not an edge. Let \(G^{\prime}\) be the graph formed from \(G\) by deleting edge \(ab\) and adding edge \(ac\). Think of this as \"flipping\" the edge \(ab\) to the edge \(ac\) as shown in Figure 7:1 Please note that in Figure 10, this corresponds to removing the edge \(qv\) and replacing it with edge \(qv^{\prime}\). Let \(C\) be any cycle in \(G\) represented by its vertices in order. We may identify cases for determining how individual cycles are changed when \(ab\) is replaced with \(ac\), by representing a cycle with a \"pattern\" that describes where \(a\), \(b\), and \(c\) occur in it, if at all. Consider, for example, the cycles of the prism graph with vertices labeled as shown in Figure 7:2  
Figure 7:3 Flipping an edge. Figure 7:4 Rethinking a vertex split. \(\{015430,0125430,0152340,0321540,\)  
\(123451,012540,015230,012340,23452,\)  
\(1251,032540,01540,0340,01230\}\)  
We identify cycles of the modified graph by following the three steps below, illustrated by the example of the cycle 015430 taken from the prism graph. Eliminate the redundant final vertex 0 in the list to obtain 01543. In this example, let \(a=1\), \(b=4\), and \(c=3\). If none of \(a,b,c\) appear in \(C\), then there is nothing to do since it remains a cycle in \(G^{\prime}\). 1. Rotate the list so that \(a\) appears first, if it occurs in the cycle, or \(b\) if it appears, or \(c\) if it appears: \(1\,54\,30\). 2. Replace the vertex numbers associated with \(a\), \(b\) and \(c\) with \"a\", \"b\" and \"c\", respectively: \(a5\,b\,c\,0\). 3. Replace the first sequence of one or more vertices not equal to \(a\), \(b\) or \(c\) with a diamond (\(\circ\)), the second if it occurs with a triangle (\(\triangle\)) and the third, if it occurs, with a square (\(\square\)): \(a\circ b\,c\,\triangle\). It helps to think of these steps as symbolic operations:  
\(15430\)  
\(a5 bc0\)  
\(a\circ bc\triangle\)  
There is no square in the above example. If we start with cycle 012543 with \(a=1\), \(b=5\), \(c=3\) we get  
\(125430\)  
\(a2b4c0\)  
\(a\circ b\triangle c\square\)  
This procedure will produce different results depending on the orientation used when enumerating the vertices in the cycle; we include all possible patterns in the case-checking in the next result for clarity's sake.