An extension to this.
How many planar graphs of vertex degrees all ≥4 are there?
Now that I have seen infinite cases (from VTand's answer), is there any way to describe all of them? i.e. Does all planar graphs that conform to the above limitations follow one of several patterns?
- Yes, and we have found all the patterns.
- No, and we have a proof.
- It is not solved (or recognized) yet.
VTand's answer:
Yes, there are infinitely many of them.
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.
I don't know how to answer your questions, but there are still many different ways to construct planar graphs each vertex of which has degree $\geq4$.
For example, if some planar graph each vertex of degree $\geq4$ has face size $4$ or more, then we can add three or four vertices and some edges so that we get a new planar graph where all vertices have degree $\geq4$. In the figure we add new vertices of blue color to the black face.
Moreover, the new graph has face of size $4$ or more again and we can continue the process of adding vertices.
Addition. However, it is possible to add three vertices to the triangle face as well, as it is done in the figure below.