Fortunately we know the following facts that if $G$ is a planar graph with minimum degree 5 then it has at least 12 vertices.
I consider 5-regular planar graph. We find a graph with 12 vertices that satisfies the conditions. By doing limited copy of following graph, we can get more 5 regular planar graphs. But what I mean is whether it is possible to find more connected 5 regular planar graphs with more than 12 vertices.
Is there any literature on this issue ? Any suggestions are valuable.
enter image description here

This question is related to the question I just asked on the forum.

Can't lower bound be improved on number of light edges in planar graph with minimum degree five?

I see this link seems to be related to my problem.

How many nodes are there in a 5-regular planar graph with diameter 2?
If G is a planar graph with minimum degree 5 then it has at least 12 vertices


1 Answer 1


The answer is yes.

Pick two copies of your graph, and draw them one next to each other.

Now, on the graph on the left erase the rightmost outside edge. On the graph on the right erase the leftmost outside edge.

Connect the top vertices and the bottom vertices of the two graphs.

It is easy to also produce such graphs from $3,4,..., n$ copies of your graph.

Ugly picture:


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .