if $G$ has average degree $d$, then there exists a subgraph with minimum degree at least $d/2$ Say we have a graph $G$ of average degree at least $d$. I want to show that we can find an induced subgraph with minimum degree at least $d/2$. The idea is to repeatedly delete vertices of degree smaller than $d/2$ from $G$, as long as there are such vertices. This should increase the average degree, but I’m not sure how to show that. First we have
$$
\frac{\sum_{i=1}^nd_i}{n}=d,
$$
where $d_i$ is the degree of the $i$th vertex. Say there exists a vertex of degree $k<d/2$. If we delete this vertex, our average degree becomes
$$
\frac{\sum_{i=1}^nd_i-2k}{n-1}.
$$
I need to show that this number is greater, using the fact that $2k<d$, but I'm not sure how. Any ideas?
 A: Oops, never mind, I figured it out! I'll post it as an answer tho:
So we need
$$
(n-1)\sum d_i<n(\sum d_i-2k),
$$
or in other words:
$$
n\sum d_i-\sum d_i<n\sum d_i-2kn\implies 2kn<\sum d_i,
$$
which is true, because $2k<\sum d_i/n=d$.
A: In fact, there is an algorithm that returns a subgraph $G'$ of $G$ where every vertex in $G'$ has degree strictly larger than $d/2$.
Let us assume that there is a vertex in $G$ of degree no larger than $d/2$ or we are done.  Let us see what happens to the average degree if we were to remove a vertex $v$ of degree $d/2$ or less from $G$. In fact, we claim that the average degree of $G' \doteq G \setminus \{v\}$ is at least $d$ if the average degree of $G$ is at least $d$. [Indeed let us write the number of vertices in $G$ as $n$. Then as $G$ has average degree at least $d$ it follows that $G$ has at least $nd/2$ edges. Then $G'$ has at least $nd/2 - d_G(v) \le$ $nd-d/2 = (n-1)d/2$ edges and $n-1$ vertices, so the average degree of $G'$ is at least $2 \times \frac{(n-1)d}{n-1} \ge d$ by the Handshaking Lemma.]
This gives an algorithm to find a subgraph $G'$ of $G$ with degree greater than $d/2$:

*

*$G' \leftarrow G$.


*WHILE there is a remove a vertex $v$ of degree $d/2$ or less in $G$:  $G' \leftarrow G' \setminus \{v\}$


*RETURN $G'$.
As each time a vertex of degree $d/2$ or less is removed from $G'$ the number of vertices goes down by 1 but the average degree stays above $d$ it follows that this will conclude with a graph where every vertex has degree strictly larger than $d/2$.
