Show there is a subgraph of G with minimum degree k Let $G$ be a simple, undirected graph with $n\ge k+1$ vertices and
\begin{align}
m\ge (k-1)(n-k-1)+{k+1 \choose 2}
\end{align}
edges.
Show there is a subgraph of $G$ with minimum degree at least $k$.
(Not necessarily looking for a full solution yet, just some hints on how to go about proving this.)

We start from $H:=G$ and to see whether there is a vertex having degree less than $k$. If there is no vertex with degree less than $k$, then we are done. If there is a vertex $v$ with degree less than $k$, then we set $H:= H-v$. Note that every time we delete a vertex, we delete at most $k-1$ many edges. Thus, if we do such deletion for $n-k-1$ times, the remaining graph will have $k+1$ vertices and at least $\binom{k+1}2$ edges, which is a $K_{k+1}$ as a subgraph of $G$.
