# How many planar graphs of vertex degrees all $\ge4$ are there?

How many planar graphs that satisfies $$\forall\ v\in V\deg(v)\ge4$$ are there?

If there are finite numbers, can you list them/link them?

If there are infinite, is there a proof?

I assume there are infinite, as if there are only a finite number, the Four Color Theorem (which led to this question) would be trivial.

• It's really not good to change a question once you've received an answer. Better to ask a new question (and link each to the other). Commented Jul 30, 2022 at 12:41
• For another infinite family, note that the edges of an octahedron form a planar graph with all vertices of degree four, and just join as many octahedra as you like together to get more examples. Commented Jul 30, 2022 at 12:43
• OK, I will do that, G.M. Commented Jul 30, 2022 at 12:51

Here's an example: a graph made of vertices arranged in a $$5 \times 5$$ square grid, and for each side of the grid, there is an extra vertex that is adjacent to all 'outer' vertices of that side.
It's quite obvious that the planar graph above satisfies the minimum degree $$4$$ requirement. In fact, as long as the grid is $$4 \times 4$$ or larger, the requirement will be satisfied. Hence, there's an infinite number of such graphs.