Prove that there exist a set $ S⊆V $ for a graph G which contains a matching M, such that there are $ frac{|E|+m}{2} $ between S and V\S

Question

Let $ G =(V,E)$ be a graph. Suppose that G contains a Matching M consisting of m edges. I have to prove that there exists a set $ S⊆V $ such that there are at least: $ \frac{|E|+m}{2} $ edges between S and V\S.

I know that it can be proven by determining the expectation of a suitable random variable, but if I choose S randomly among all subsets of V it is only suffice to obtain $\frac{|E|}{2} $ edges.

Any tips how to determine such a suitable random variable?

Thank you in advance :)

Answer 1

For every edge $vw$ of the matching, flip a coin to put either $v$ or $w$ in $S$.

For all vertices not in the matching, proceed as usual and flip a coin to decide if they're in $S$ or not.