# Constructing Minimally 3-Connected Graphs
## 5 Isomorph-Free Graph Construction
### Infinite Bookshelf Algorithm
The set of three vertices is 3-compatible because the degree of each vertex in the larger class is exactly 3, so that any chording edge cannot be extended into a chording path connecting vertices in the smaller class, as illustrated in Figure 17.

If \(G\) has a prism minor, by Theorem 7, with the prism graph as \(H\), \(G\) can be obtained from a 3-connected graph with \(n-1\) vertices and \(m-1\) edges via an edge addition and a vertex split, from a graph with \(n-2\) vertices and \(m-3\) edges via two edge additions and a vertex split, or from a graph with \(n-1\) vertices and \(m-3\) edges via an edge addition and two vertex splits; that is, by operation D1, D2, or D3, respectively, as expressed in Theorem 8. By Theorem 6, all minimally 3-connected graphs can be obtained from smaller minimally 3-connected graphs by applying these operations to 3-compatible sets. We constructed all non-isomorphic minimally 3-connected graphs up to 12 vertices using a Python implementation of these procedures. The total number of minimally 3-connected graphs for 4 through 12 vertices is published in the Online Encyclopedia of Integer Sequences. Table 1 below lists these values. These numbers helped confirm the accuracy of our method and procedures. The number of non-isomorphic 3-connected cubic graphs of size \(n\), where \(n\) is even, is published in the Online Encyclopedia of Integer Sequences as sequence A204198. This sequence only goes up to \(n=14\). We were able to obtain the set of 3-connected cubic graphs up to 20 vertices as shown in Table 2. \begin{table}
\begin{tabular}{c c} \hline \hline \(n\) & **Minimally 3-Connected Graphs (A199676)** \\ \hline
6 & 3 \\ \hline
7 & 5 \\ \hline
8 & 18 \\ \hline
9 & 57 \\ \hline
10 & 285 \\ \hline
11 & 1513 \\ \hline
12 & 9824 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: 3-connected graphs and minimally 3-connected graphs graphs from oeis.org. Figure 17: \(K_{3,5}\) with a cycle highlighted in black and a chording edge highlighted in gray. All of the minimally 3-connected graphs generated were validated using a separate routine based on the Python iGraph ([[https://igraph.org/python/](https://igraph.org/python/)]([https://igraph.org/python/](https://igraph.org/python/))) vertex_disjoint_paths method, in order to verify that each graph was 3-connected and that all single edge-deletions of the graph were not. The overall number of generated graphs was checked against the published sequence on OEIS. The 3-connected cubic graphs were verified to be 3-connected using a similar procedure, and overall numbers for up to 14 vertices were checked against the published sequence on OEIS. The minimally 3-connected graphs were generated in 31 h on a PC with an Intel Core I5-4460 CPU at 3.2 GHz and 16 Gb of RAM. The 3-connected cubic graphs were generated on the same machine in five hours. The algorithm's running speed could probably be reduced by running parallel instances, either on a larger machine or in a distributed computing environment. MapReduce, or a similar programming model, would need to be used to aggregate generated graph certificates and remove duplicates. It is also possible that a technique similar to the canonical construction paths described by [PERSON], [PERSON] and [PERSON] [11] could be used to reduce the number of redundant graphs generated. Even with the implementation of techniques to propagate cycles, the slowest part of the algorithm is the procedure that checks for chording paths. It may be possible to improve the worst-case performance of the cycle propagation and chording path checking algorithms through appropriate indexing of cycles. The code, instructions, and output files for our implementation are available at [[https://github.com/rkingan/m3c](https://github.com/rkingan/m3c)]([https://github.com/rkingan/m3c](https://github.com/rkingan/m3c)). The output files have been converted from the format used by the program, which also stores each graph's history and list of cycles, to the standard graph6 format, so that they can be used by other researchers.