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

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..."

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.