State and prove Hall's theorem, giving any definitions required by the proof (e.g. of an $M$-alternating path).

Let $G=(V, E)$ be a (not necessarily bipartite) graph, and let $\gamma(G)$ be the size of the largest matching in $G$. Let $\beta(G)$ be the smallest $k$ for which there exist $k$ vertices $v_{1}, \ldots, v_{k} \in V$ such that every edge in $G$ is incident with at least one of $v_{1}, \ldots, v_{k}$. Show that $\gamma(G) \leqslant \beta(G)$ and that $\beta(G) \leqslant 2 \gamma(G)$. For each positive integer $k$, find a graph $G$ with $\beta(G)=2 k$ and $\gamma(G)=k$. Determine $\beta(G)$ and $\gamma(G)$ when $G$ is the Turan graph $T_{3}(30)$ on 30 vertices.

By using Hall's theorem, or otherwise, show that if $G$ is a bipartite graph then $\gamma(G)=\beta(G) .$

Define the chromatic index $\chi^{\prime}(G)$ of a graph $G$. Prove that if $n=2^{r}$ with $r \geqslant 1$ then $\chi^{\prime}\left(K_{n}\right)=n-1$.