Reduce degree of each vertex by at least $1$ but keep minimum degree large? Let $G=(V,E)$ be a graph with minimum degree $\delta_G>10$.
Can we always remove some edges to get a graph $G'$ with minimum degree at least $\delta/2$, but $\deg_{G'}(v) \leq \deg_{G}(v)-1$ for all $v\in V$?
This is not an exercise problem, but it was motivated from an exercise problem, in Chapter 1 of Alon and Spercer's The Probabilistic Methods.
I guess I am supposed to show what I have tried, but sadly I have little idea on how to start... Any hints or reference will be good.
 A: The following will do what you ask if $G$ has minimum degree $\delta(G)\ge4.$
Theorem. Given a graph $G$ with no isolated vertices, we can find a spanning subgraph $H,$ with minimum degree $\delta(H)\ge\delta(G)-2,$ such that $\deg_H(v)\lt\deg_G(v)$ for each vertex $v.$
Proof. Let $\delta=\delta(G).$ First, suppose $G$ is $\delta$-regular. By Vizing's theorem, $G$ has a proper edge coloring with $\delta+1$ colors. Choose such a coloring, and then remove all edges of two chosen colors, resulting in a spanning subgraph $H.$ Since each vertex is incident with one or two edges of the chosen colors, $H$ has the desired properties.
Now suppose $G$ has vertices of degree greater than $\delta.$ Let $v$ be such a vertex. Choose some edge incident with $v,$ say $e=uv,$ and temporarily detach it from $v,$ leaving it attached to $u.$ (If you don't like half-edges, create a new vertex $v'$ and replace the edge $uv$ with $uv'.$) Repeat this procedure as needed, until there are no vertices of degree greater than $\delta.$ Now apply Vizing's theorem as before, to get a proper edge coloring with $\delta+1$ colors; then restore the graph to its original state and remove all edges of two chosen colors.
