(i) State and prove Hall's theorem concerning matchings in bipartite graphs.

(ii) The matching number of a graph $G$ is the maximum size of a family of independent edges (edges without shared vertices) in $G$. Deduce from Hall's theorem that if $G$ is a $k$-regular bipartite graph on $n$ vertices (some $k>0$ ) then $G$ has matching number $n / 2$.

(iii) Now suppose that $G$ is an arbitrary $k$-regular graph on $n$ vertices (some $k>0)$. Show that $G$ has a matching number at least $\frac{k}{4 k-2} n$. [Hint: Let $S$ be the set of vertices in a maximal set of independent edges. Consider the edges of $G$ with exactly one endpoint in $S$.]

For $k=2$, show that there are infinitely many graphs $G$ for which equality holds.