# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### The Algorithm Is Isomorph-Free  
To make the process of eliminating isomorphic graphs by generating and checking nauty certificates more efficient, we organize the operations in such a way as to be able to work with all graphs with a fixed vertex count \(n\) and edge count \(m\) in one batch. Specifically, for an \(m,n\) combination, we define sets \(A^{(*)}_{m,n}\), where \(*\) represents 0, 1, 2, or 3, \(B_{m,n}\) and \(C_{m,n}\) as follows:  
* \(A^{(0)}_{m,n}\) only ever contains of the \"root\" graph; i.e., the prism graph. So for values of \(m\) and \(n\) other than 9 and 6, \(A^{(0)}_{m,n}=\varnothing\). All graphs in \(A^{(0)}_{m,n}\), \(A^{(1)}_{m,n}\), \(A^{(2)}_{m,n}\), and \(A^{(3)}_{m,n}\) are minimally 3-connected.
* \(B_{m,n}\) consists of graphs generated by adding an edge to a minimally 3-connected graph with \(m-1\) vertices and \(n\) edges.
* \(C_{m,n}\) consists of graphs generated by adding an edge to a graph in \(B_{m-1,n}\) that is incident with the edge added to form the input graph.
* \(A^{(1)}_{m,n}\) consists of graphs generated by splitting a vertex in a graph in \(B_{m-1,n-1}\) that is incident to the edge added to form the input graph, after checking for 3-compatibility.
* \(A^{(2)}_{m,n}\) consists of graphs generated by splitting a vertex in a graph in \(A^{(1)}_{m-1,n-1}\) that is incident to the same edge as the vertex split to form the input graph, after checking for 3-compatibility.  
Figure 14: Infinite bookshelf approach to minimizing isomorphism checking.  
* \(A_{m,n}^{(3)}\) consists of graphs generated by splitting a vertex in a graph in \(C_{m-1,n-1}\) that is incident to the two edges added to form the input graph, after checking for 3-compatibility. Then, beginning with \(m=10\) and \(n=6\), we construct graphs in \(C_{m,n}\), \(B_{m,n}\), \(A_{m,n}^{(1)}\), \(A_{m,n}^{(2)}\) and \(A_{m,n}^{(3)}\), in that order, from input graphs with \(m-1\) vertices and \(n\) edges, and with \(m-1\) vertices and \(n-1\) edges. As graphs are generated in each step, their certificates are also generated and stored. Any new graph with a certificate matching another graph already generated, regardless of the step, is discarded, so that the full set of generated graphs is pairwise non-isomorphic. At the end of processing for one value of \(n\) and \(m\) the list of certificates is discarded. For any value of \(n\), we can start with \(m=n+4\) and proceed until no more graphs or generated or, when \(n\geq 8\), when \(m=3n-7\). By Theorem 3, no further minimally 3-connected graphs will be found after \(m=3n-9\) when \(n\geq 8\); however we still need to generate single- and double-edge additions to be used when considering graphs with \(n+1\) vertices. Proceeding in this fashion, at any time we only need to maintain a list of certificates for the graphs for one value of \(m\) and \(n\). The generation sources and targets are summarized in Figure 15, which shows how the graphs with \(n\) vertices and \(m\) edges, in the upper right-hand box, are generated from graphs with \(n\) vertices and \(m-1\) edges in the upper left-hand box, and graphs with \(n-1\) vertices and \(m-1\) edges in the lower left-hand box.