There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?

Question

Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?

Answer 1

There is a 3-connected 5-regular simple $n$-vertex planar graph if and only if $n=12$ or $n \ge 16$ is even. See Recursive generation of 5-regular graphs by Mahdieh Hasheminezhad, Brendan D. McKay, Tristan Reeves in WALCOM: Algorithms and Computation, eds. Das and Uehara, Lecture Notes in Computer Science, vol 5431, Springer 2009. The number of such graphs is given in OEIS A308489.

They use a set of 7 graphs that are irreducible under a system of expansions & reductions and, as is common for contemporary graph theory, computer assistance. E.g., "The program completed execution in 21 seconds. In total, 39621 induced subgraphs were found..."

Answer 2

There are no such graphs when $n$ is odd, by the handshaking lemma.

Conversely, for all even $n \geq 224$, we claim such a graph exists.

In particular, given two planar 5-regular graphs $G$, $H$ each drawn on the surface of a sphere, we can define the 'connected sum' of the graphs as follows:

• remove a small disk (containing one vertex) from the sphere on which $G$ is drawn;
• remove a small disk (containing one vertex) from the sphere on which $H$ is drawn;
• combine the two resulting hemispheres at their equator.

The resulting graph (which may depend on the chosen vertices) has $|G| + |H| - 2$ vertices, and inherits the planarity, 5-regularity, and 3-connectedness of $G$ and $H$.

Now, given an even integer $n \geq 224$, we can find integers $i, j \geq 0$ such that $n = 2 + 10i + 58j$. Then we can construct an $n$-vertex graph with the desired properties by taking the connected sum of $i$ copies of the icosahedron and $j$ copies of the snub dodecahedron.

---

This leaves finitely many values of $n$ to check, namely the even numbers between 14 and 222.