Construct a class of maximal planar graphs with exactly 4 vertices of degree 3.

graph theoryplanar-graphs

The post is very interesting, and it tells us that any planar graph with at least $4$ vertices has at least $4$ vertices of degree $5$ or less. Recently, I also saw a question on a Chinese forum (written in Chinese) that asked for a further question.

Does a planar graph with $p\ge 5$ vertices have at least 5 vertices with
degree $≤ 5$?

I believe the answer to this question is negative because I have observed many counterexamples to it (using the nice software CaGe). For example, in some maximal planar graphs, only 4 vertices have degree 3, and all other vertices have degree 6.

enter image description here

enter image description here

However, it would be more convincing to provide a class of infinitely many examples that refute it.

So my question is: Is it possible to construct a class of maximal planar graphs where only 4 vertices have degree 3, and all other vertices have degree 6?

Those lower-order graphs may be helpful in constructing more general examples, but I haven't figured out how to utilize them at the moment.

Best Answer

Yes.

Start with a maximal planar graph that already has this property (for example, $K_4$ trivially has this property).

Now you subdivide each edge $uv$ twice, adding degree 2 vertices $x$ and $y$. Further, add a vertex $w$ to every face of the planar graph. You will now add every edge of the form $wx$ and $wy$ (leaving $w$ with degree 6, and $x$, $y$ with degree 5). You will also add edges between the $x$' vertices on the same face, and the $y$' vertices on the same face to get these up to degree 6.

This should work for any starting graph to add only vertices of degree 6.

See the diagram below for how to do this step by step on $K_4$:

enter image description here

The blue vertices are $w$ vertices, red vertices are $x$ and $y$ vertices. There are 6 blue edges for each $w$ vertex, and 2 original black edges, 2 blue edges, 2 red edges for each edge among $x$ and $y$ type vertices.

EDIT: Of course, to get the entire infinite class, you repeat this construction again and again on the previously obtained graph.