State and prove Hall's theorem about matchings in bipartite graphs.

Show that a regular bipartite graph has a matching meeting every vertex.

A graph is almost r-regular if each vertex has degree $r-1$ or $r$. Show that, if $r \geqslant 2$, an almost $r$-regular graph $G$ must contain an almost $(r-1)$-regular graph $H$ with $V(H)=V(G)$.

[Hint: First, if possible, remove edges from $G$ whilst keeping it almost r-regular.]