Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / A / 1 / b

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|\le |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|)\ge 2009$ 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 perfect matching avoiding every edge of $F$.