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.

enter image description here

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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – kabenyuk
    Sep 26, 2023 at 15:36

1 Answer 1


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.


You must log in to answer this question.

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