If $|E(G)|\ge(k-1)|V(G)|$ then $G$ has a subgraph $H$ such that $\delta(H)\ge k$ for $k\ge 2$

Question

I don't understand a proof of the fact above:

Let $H$ be a subgraph of $G$ such that $\frac{|E(H)|}{|V(H)|}$ is maximal, and if there are many canditates chose $H$ with a minimal number of vertices. Then $\frac{|E(H)|}{|V(H)|}\ge \frac{|E(G)|}{|V(G)|}\ge k-1$

Suppose that there is a $v\in V(H)$ s.t. $d_H(v)\le k-1$

Let $H'$ be the graph resulting from removing $v$ from $H$. We have $\begin{cases}|E(H')|\ge|E(H)|-(k-1) \\ |V(H')|=|V(H)|-1 \end{cases}$ $\implies \frac{|E(H')|}{|V(H')|}\ge \frac{|E(H)|}{|V(H)|}$

-Why do we have the last equality?

-Shouldn't it be a strict inequality in order to have contradiction?

Here $\delta(G)=\min\{d(v)\ : v\in V(G)\}$ and $d_H(v)=\text{degree of v in H}$

Answer 1

We get $\frac{|E(H')|}{|V(H')|} \ge \frac{|E(H)|}{|V(H)|}$ because we know $\frac{|E(H)|}{|V(H)|} \ge \frac{|E(G)|}{|V(G)|} \ge k-1$, so $$ \frac{|E(H')|}{|V(H')|} \ge \frac{|E(H)| - (k-1)}{|V(H)|-1} \ge \frac{|E(H)| - \frac{|E(H)|}{|V(H)|}}{|V(H)|-1} = \frac{|E(H)|}{|V(H)|}. $$

It doesn't have to be a strict inequality to obtain a contradiction, because when there are many candidates, we choose $H$ with the minimum number of vertices. If $\frac{|E(H')|}{|V(H')|} = \frac{|E(H)|}{|V(H)|}$, then we still get a contradiction, because $H'$ has fewer vertices than $H$, so we would have chosen $H'$ rather than $H$ in the first step.

(You can also formulate the proof differently: for as long as there is a vertex of degree $k-1$ or less, you can delete it and get another, smaller graph $G'$ with $|E(G')| \ge (k-1)|V(G')|$. This process can't keep going forever, because there's only finitely many vertices, so it must stop: and when it stops, it must be because the minimum degree is at least $k$.)

Answer 2

From this two inequalties we obtain $$ \frac{|E(H')|}{|V(H')|}\geq \frac{|E(H)|-(k-1)}{|V(H)|-1}, $$ so we need to prove that $$ \frac{|E(H)|-(k-1)}{|V(H)|-1}\geq \frac{|E(H)|}{|V(H)|}. $$ The last inequality is equivalent to $$ (|E(H)|-(k-1))\cdot|V(H)|\geq |E(H)|\cdot (|V(H)|-1), $$ or to $$ |E(H)|\geq (k-1)\cdot |V(H)|, $$ which is true due to assumption $\frac{|E(H)|}{|V(H)|}\geq k-1$.

Therefore, we have a subgraph $H'$ with the property $\frac{|E(H')|}{|V(H')|}\ge \frac{|E(H)|}{|V(H)|}$, which is possible only in case $\frac{|E(H')|}{|V(H')|}= \frac{|E(H)|}{|V(H)|}$ (because we choose $H$ as a subgraph $G$ with the minimal value of $\frac{|E(H)|}{|V(H)|}$). However, $H'$ has less vertices than $H$, so we get a contradiction.