7
$\begingroup$

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

$\endgroup$

2 Answers 2

10
$\begingroup$

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

$\endgroup$
1
10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ great answer! Great that you present this simple construction $\endgroup$
    – Béart
    Jul 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.