Perfect matching in a bipartitite graph

Question

Prove that for every $r$-regular bipartite graph $G$ and for every set $X$ of at most $r − 1$ edges, $G − X$ has a perfect matching.

Answer 1

By Hall's Theorem, an $r$-regular bipartite graph $G$ has a perfect matching $M$. Notice that $G-M$ is $(r-1)$-regular and bipartite, so $G-M$ has a perfect matching. We can peel off perfect matchings $r$ many times, obtaining $r$ perfect matchings. As mentioned in the comments, this yields a $1$-factorization.

If you remove $m$ edges from $G$, you can only ever hope to "break" at most $m$ matchings in $G$ (each one of your edges can correspond to at most $1$ of the $r$ matchings, never $2$ or more.) So removing $(r-1)$-edges still leaves us with $1$ perfect matching.