2
$\begingroup$

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.

$\endgroup$
1
  • 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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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