Density of bipartite $d$-degenerate graph

Question

A graph $G$ is $d$-degenerate if every subgraph of $G$ contains a vertex of degree at most $d$. It is known that an $n$-vertex $d$-degenerate graph has at most $d(n-1)$ edges. However, if we are given a bipartite $d$-degenerate graph $(H:m,n)$, what is its maximum number of edges?

Answer 1

Theorem. A $d$-degenerate $n$-vertex bipartite graph has at most $\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor$ edges if $n < 2d$ and at most $d(n-d)$ edges if $n \geq 2d$. Moreover, both these bounds are tight.

Proof. Suppose $G$ is a $d$-degenerate $n$-vertex bipartite graph. Every $n$-vertex bipartite graph contains at most $\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor$ edges. If $n \leq 2d$, then $K_{\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor}$ is $d$-degenerate, so this bound is tight. If $n \geq 2d$, we proceed by induction on $n$. The base case of $n=2d$ has already been established by the previous argument. Thus, we may assume that $n > 2d$. Let $x$ be a vertex of degree at most $d$ in $G$. By induction, $G-x$ contains at most $d(n-1-d)$ edges, so $G$ has at most $d(n-d)$ edges. This bound is tight as demonstrated by $K_{d, n-d}$. $\square$

Note that if $d$ is a constant, then the bound is not much better than for general graphs. A $d$-degenerate graph contains at most $\binom{n}{2}$ edges if $n \leq d$ and at most $d(n-d)+\binom{d}{2}$ edges if $n > d$. These bounds are tight, since $K_n$ is $d$-degenerate if $n \leq d$ and the join of $K_d$ and a stable set of size $n-d$ is $d$-degenerate if $n > d$.