= Solution
Write the bipartition as $L,R$. Counting edges by their left and right ends gives $2009|L|=2009|R|$, so the parts have equal size. Put $H=G-F$. If some $S\subseteq L$ violated <Hall's marriage theorem> in $H$, let $T=N_H(S)$, so $|T|\leq|S|-1$.
There are $2009|S|$ edges of $G$ incident with $S$, of which at most $2009|T|$ can end in $T$. Thus at least $2009(|S|-|T|)\geq2009$ end in $R\setminus T$. All those edges must have been deleted, by the definition of $T$. This contradicts $|F|=2008$. Hence $H$ has a <matching> covering $L$, and equal part sizes make it a \b[<perfect matching> avoiding every edge of $F$].
Back to article page
