*Proof 1 of Statement B for regular graphs.* Let $\Gamma$ be a regular graph of degree $d$. As in F. Petrov's answer to https://mathoverflow.net/questions/362168/existence-of-connected-component-with-large-boundary : by Kleitman and West (https://epubs.siam.org/doi/10.1137/0404010), there exists a spanning tree with $\geq n/4$ leaves, where $n=|V|$. Define $S$ to be the set of non-leaves. Then the total degree of the elements of $V\setminus S$ (that is, the leaves) is $\geq d n/4 = |E|/4$.

*Proof 2 of Statement B for regular graphs (from scratch, inspired by Kleitman-West - TL;DR greedy algorithm).*  I thought I had a different proof, but I no longer do, or rather, the proof, when corrected, is not really different from Kleitman-West after all.

More to the point: it seems that a proof along these lines is not going to generalize easily to the non-regular case. 
It is clear that, for $\Gamma$ not regular, the greedy algorithm could incur a loss at some point and fail to recoup it for more than $C$ steps, for any absolute constant $C$: consider a complete graph of high degree surrounded by many layers of vertices of low degree.