MathNet 2018-part-07 — 177 problems (EN–VI) Question 137

Evan has a simple graph with $v$ vertices and $e$ edges. Show that he can delete at least $\frac{e-v+1}{2}$ edges so that each vertex still has at least half of its original degree.