Given a graph $G$ and a vertex $u$ in it, let $N(u)$ denote the set of neighbours of $u$ in $G$. A graph $G$ having $n$ vertices is said to be $k$ degenerate if there is a linear ordering $v_{1}, v_{2}, \ldots, v_{n}$ of the vertices, in which each vertex has at most $k$ neighbours after it. That is, for all $i \in\{1,2, \ldots, n\},\left|\left\{v_{j} \in N\left(v_{i}\right): j>i\right\}\right| \leq k$.
- Calculate the maximum number of edges possible in a $k$-degenerate graph having $n$ vertices.
- Let $H$ be any graph. Let $H^{\prime}$ be the graph obtained by removing a vertex of degree at most $k$ from $H$. Prove that $H$ is $k$-degenerate if and only if $H^{\prime}$ is $k$-degenerate.
