Let $G$ be a bipartite graph with vertex classes $X$ and $Y$, each of size $n$. State and prove Hall's theorem giving a necessary and sufficient condition for $G$ to contain a perfect matching.

A vertex $x \in X$ is flexible if every edge from $x$ is contained in a perfect matching. Show that if $|\Gamma(A)|>|A|$ for every subset $A$ of $X$ with $\emptyset \neq A \neq X$, then every $x \in X$ is flexible.

Show that whenever $G$ contains a perfect matching, there is at least one flexible $x \in X$.

Give an example of such a $G$ where no $x \in X$ of minimal degree is flexible.