Upper bound for the degeneracy of maximal planar bipartite graphs I understand that the degeneracy of a complete bipartite graph $K_{m,n}$ is $\delta(K_{m,n})=\min\{m,n\}$. However, I am trying to look bounds for the degeneracy of maximal planar bipartite graphs. I understand that planar bipartite graphs cannot contain $K_{3,3}$ or $K_{5}$ as a minor, but I am struggling to come up with proper bounds for my case, since I feel like something else is required here.
Obviously $\min\{m,n\}$ works as an upper bound for a bipartite graph where the partite sets have cardinalities of $m$ and $n$. This being said, it would be nice to improve this bound. I am not interested in the lower bound for the degeneracy of such graphs though (since this seems trivial), but improvements on this upper bound would be nice.
The big thing here is that these graphs are maximal planar, which means that if we add one more edge to these graphs, they are no longer planar. This is why the bound $\min\{m,n\}$ seems to only be tight in the case when the graph does not contain $K_{3,3}$ as a minor.
 A: Just a misconception to clear up: you can add an edge to a maximal planar bipartite graph (MPBG) and still have a planar graph, it just won't be bipartite anymore! (you can also add edges that keep it bipartite, but destroy planarity).
Structurally, MPBGs are quite nice - they are graphs in which every face is a square (i.e., every face is bounded by a 4-cycle). The one exception to this is the collection of star graphs $K_{1,n}$.
Let $G$ be an MPBG. You can use this fact that each face is bounded by $4$ edges - and the Euler Characteristic Equation - to count the number of edges in $G$. You should find that an MPBG with $n$ vertices has $m = 2n - 4$ edges. Thus, every planar bipartite graph with $n'$ vertices (including any subgraph of $G$) has $m'\leq 2n' - 4$ edges. So the average degree of any subgraph of $G$ is at most $\frac{4n'-8}{n'} < 4$, from which it follows that the minimum degree of the subgraph satisfies $\delta \leq 3$.
There are MPBGs with $\delta = 3$ exactly (such that the cube $Q_3 = K_2\times K_2 \times K_2$), demonstrating that this bound is sharp.
