Existence of induced subgraph with desired properties

Question

I was reading the proof of the following proposition

This proof is not detailed so I've decided to provide some details to understand it better. For convenience assume that $G_0:=G$ and $|V_{G_0}|>1$.

1. If for all $v\in V_{G_0}$ we have $d_{\text{ave}}(G_0-v)<d_{\text{ave}}(G_0)$ (which is equivalent to $d(v)>\frac{1}{2}d_{\text{ave}}(G_0)$), then we can take $H$ to be $G_0$.

2. If for some $v_0\in V_{G_0}$ we have $d_{\text{ave}}(G_0-v_0)\geq d_{\text{ave}}(G_0)$ (which is equivalent to $d(v_0)\leq\frac{1}{2}d_{\text{ave}}(G_0)$), then we delete vertex $v_0$ and consider the graph $G_1:=G_0-v_0$.

We apply the same procedure to $G_1$.

So my question is the following: Is it possible that we will end up with empty set? Suppose it is, then we'll get a sequence of vertices $\{v_k\}_{k=0}^{n-1}$ (where $|V_{G_0}|=n$) such that $v_k\in V_{G_k}$ where $G_{k+1}:=G_k-v_k$ such that $d(v_k)\leq \frac{1}{2}d_{\text{ave}}(G_k)$ for $k=0,\dots,n-1$.

Is it possible to derive some contradiction here?

Answer 1

At each step, the average degree of $G_k$ is at least the average degree of $G$, so it is not possible to delete all but one vertex of $G$, as a single vertex graph has average degree $0$.