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?
[Math] if $G$ has average degree $d$, then there exists a subgraph with minimum degree at least $d/2$
graph theory
Best Answer
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$.