KöMaL 2011 A535

There is given a simple graph $G$ with vertices $v_1$,...,$v_n$. $H_1$,...,$H_n$ are sets of nonnegative integers such that for every $i$=1,2,...,$n$, the cardinality of $H_i$ is at most half of the degree of $v_i$. Prove that $G$ contains a subgraph $G$' with the same vertices such that the degree of $v_i$ in $G$' is not an element of $H_i$ for any $i$.