My question was partly inspired by the question linked below.

I see a wonderful construction of Adam P. Goucher, which guarantees that 3-connected 5-regular planar graphs are infinitely numerous. I wonder if there is a similar construct for the 5-connected 5-regular planar graphs. (Maybe I don't need to generate all of them like the title of this post.)

enter image description here

I noted the number of 5-connected 5-regular planar graphs with at most 36 vertices in the following paper.

  • Hasheminezhad M, McKay B, Reeves T. Recursive generation of simple planar 5-regular graphs and pentangulations[J]. 2011.

enter image description here

Enough such graphs to convince me there are an unlimited number of such graphs. And when $n$ is large enough, for every $n$ there is a graph that I want.

  • $\begingroup$ Surely the exact same construction works? $\gcd(16-2,18-2) = 2$ and the Frobenius number of 7 and 8 is 41 so there's a graph for any even $n \ge 86$. $\endgroup$ Jun 15, 2022 at 14:26
  • $\begingroup$ Unfortunately, I'm not sure if the same construction can keep the new graph 5-connected. $\endgroup$
    – L.C. Zhang
    Jun 15, 2022 at 14:32

1 Answer 1


The answer is yes.

This construction is from the paper "Pairs of Hamiltonian circuits in 5-connected planar graphs" by Joseph Zaks. This is the "connected sum" of a 5-regular planar graph with an icosahedral graph.

graph substitution

Let $G$ be a 5-valent 5-connected planar graph and $v$ a vertex of it. Replace $v$ by the 11-vertex graph shown above. The new graph is 5-valent, 5-connected, planar and has 10 more vertices. Thus there is an infinitude of such graphs.


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.