# Is there a way to generate all 5-connected 5-regular planar graphs?

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

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.

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.

• 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$. Jun 15, 2022 at 14:26
• Unfortunately, I'm not sure if the same construction can keep the new graph 5-connected.
– lcz
Jun 15, 2022 at 14:32

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.