Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
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..."
2$\begingroup$ Those up to 36 vertices are at users.cecs.anu.edu.au/~bdm/data/planegraphs.html . $\endgroup$ Jul 22, 2020 at 10:01
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.
$\begingroup$ great answer! Great that you present this simple construction $\endgroup$– BéartJul 22, 2020 at 9:39
1$\begingroup$ Fun application of the Frobenius problem going from $2+10i+58j$ to 224. Using your construction with the icosahedron and the 16-vertex graph Brendan & collaborators found covers graphs with $n = 2+10i+14j$ vertices and brings the cases to check down to 14, 18, 20, 24, 28, 34, 38, 48. $\endgroup$ Jul 23, 2020 at 1:13