# Maximum number of vertices with degree three in maximal bipartite planar graphs

A bipartite graph $$G$$ is a graph where each cycle has an even length. If $$G$$ can be drawn on the plane without any crossings of edges, $$G$$ is called planar. $$G$$ is called maximal planar bipartite if it has the property that if we add an edge (without adding vertices) to $$G$$, we obtain a graph that is no longer planar or bipartite.

Apart from star graphs, a maximal planar bipartite graph divides the plane into quadrangles only. See the figure below.

Let $$G$$ be an $$n$$-vertex maximal planar bipartite graph with minimum degree 3. Let $$n_3$$ be the number of vertices of degree 3 in $$G$$. It is easy to know $$G$$ has exactly $$2n-4$$ edges. So $$3n_3+4(n-n_3)\le 2(2n-4)$$, we have $$n_3\ge 8$$. But how about upper bounds on $$n_3$$? A more formal question ：

Question: Let $$G$$ be an $$n$$-vertex maximal planar bipartite graph with minimum degree 3. Then what is the maximum number of vertices of degree 3 in $$G$$?

Here is some analysis:

If, in $$G$$, all vertices except the 3-degree vertices are 4-degree vertices, we quickly deduce that $$n_3=8$$. If, on the other hand, all vertices except the 3-degree vertices are 5-degree vertices, we have $$3n_3+5(n-n_3)=4n-8$$, which implies $$n_3=\frac{n-8}{2}$$. Then will $$\frac{n-8}{2}$$ be the best upper bound?

I'm not sure if this problem is at a research level or just a routine exercise. It stemmed from my casual thoughts. Or it's possible that this question has already been solved somewhere.

• I corrected a small inaccuracy in one of your formulas. And then there's this. If I am not mistaken every maximal planar bipartite graph is a quadrangulation and inversely every quadrangulation is a maximal planar bipartite graph. So the answer to your question should be found in the works devoted to quadrangulations. Sep 26, 2023 at 15:36

Taking the dual would give us a $$4$$-regular planar graph where we want as many of the faces as possible to be triangles. There's a family of $$4$$-regular polyhedra where almost all faces are triangles: the antiprisms. So the dual of an antiprism (apparently, this is called a trapezohedron) should be a good candidate for reaching the upper bound here.

For any even $$n$$, the dual of the antiprism consists of an $$(n-2)$$-cycle with two more vertices: one adjacent to every even vertex of the cycle, and one adjacent to every odd vertex. This has two vertices of degree $$\frac n2-1$$, and $$n-2$$ vertices of degree $$3$$. (When $$n=8$$, all $$n$$ vertices have degree $$3$$, and this graph is just the cube.)

Except when $$n=8$$, we cannot have $$n$$ vertices of degree $$3$$, but it's conceivable that we can have $$n-1$$ vertices of degree $$3$$ and one vertex of degree $$n-5$$. Let's analyze this case.

Let $$v$$ be the vertex of degree $$n-5$$. We know the bipartition, up to two cases: if we put $$v$$ on one side, and its $$n-5$$ neighbors on the other, then either the remaining $$4$$ vertices are all on the same side as $$v$$, or one of them is on the side with $$v$$'s neighbors and adjacent to the other $$3$$. In the first case, counting the edges from each side, we want $$(n-5) + 4\cdot 3 = (n-5) \cdot 3$$, so $$n=11$$. This is impossible by computer search, and there should be a combinatorial proof, but I haven't found a clean argument. In the second case, we want $$(n-5) + 3 \cdot 3 = (n-4) \cdot 3$$, so $$n=8$$, and that's the cube again.

One remaining question: can we have $$n-2$$ vertices of degree $$3$$ when $$n$$ is odd? Experimentally, no: here's a table of the maximum value of $$n_3$$ for small odd $$n$$.

$$\begin{array}{c|ccccccc} n & 11 & 13 & 15 & 17 & 19 & 21 \\ \hline n_3 & 8 & 10 & \color{red}{11} & 14 & 16 & \color{red}{17} \end{array}$$

For $$n=15$$ and $$n=21$$, we can't even get to $$n-3$$ vertices of degree $$3$$.

There's a reason to expect a repeating pattern mod $$6$$: if you can get a solution for $$n$$ where two vertices $$v,w$$ of degree greater than $$3$$ share a face but are not adjacent, you can get a solution for $$n+6$$ by adding a cube graph on $$v$$, $$w$$, and $$6$$ new vertices, and this can be iterated. It's hard to say what's up with the upper bounds, though.