if $G$ has average degree $d$, then there exists a subgraph with minimum degree at least $d/2$

Question

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?

Answer 1

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

Answer 2

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

1. $G' \leftarrow G$.

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

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