Return to Answer

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, since $d$-generate graphs contain at most $d(n-d)+\binom{d}{2}$ edges. This is tight, as the graph which is the join of $K_d$ and a stable set of size $n-d$ shows.

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$.

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 with bipartition $(X,Y)$. If $n \leq 2d$, then $|X| \leq d$ or $|Y| \leq d$. Thus, we may assume that $G$ is a complete bipartite graph. The number of edges of $G$ is maximized when $|X|=\lceil \frac{n}{2} \rceil$. 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, since $d$-generate graphs contain at most $d(n-d)+\binom{d}{2}$ edges. This is tight, as the graph which is the join of $K_d$ and a stable set of size $n-d$ shows.

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, since $d$-generate graphs contain at most $d(n-d)+\binom{d}{2}$ edges. This is tight, as the graph which is the join of $K_d$ and a stable set of size $n-d$ shows.

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 with bipartition $(X,Y)$. If $n \leq 2d$, then $|X| \leq d$ or $|Y| \leq d$. Thus, we may assume that $G$ is a complete bipartite graph. The number of edges of $G$ is maximized when $|X|=\lceil \frac{n}{2} \rceil$. 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 the bound is not much better than for general graphs, since the same proof shows that $d$-generate graphs contain at most $d(n-d)+\binom{d}{2}$ edges. This is tight, as the graph which is the join of $K_d$ and a stable set of size $n-d$ shows.

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 with bipartition $(X,Y)$. If $n \leq 2d$, then $|X| \leq d$ or $|Y| \leq d$. Thus, we may assume that $G$ is a complete bipartite graph. The number of edges of $G$ is maximized when $|X|=\lceil \frac{n}{2} \rceil$. 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, since $d$-generate graphs contain at most $d(n-d)+\binom{d}{2}$ edges. This is tight, as the graph which is the join of $K_d$ and a stable set of size $n-d$ shows.