Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. What does it mean to say that $G$ contains a matching from $X$ to $Y$ ?

State and prove Hall's Marriage Theorem, giving a necessary and sufficient condition for $G$ to contain a matching from $X$ to $Y$.

Now assume that $G$ does contain a matching (from $X$ to $Y$ ). For a subset $A \subset X$, $\Gamma(A)$ denotes the set of vertices adjacent to some vertex in $A$.

(i) Suppose $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$. Show that every edge of $G$ is contained in a matching.

(ii) Suppose that every edge of $G$ is contained in a matching and that $G$ is connected. Show that $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$.

(iii) For each $n \geqslant 2$, give an example of $G$ with $|X|=n$ such that every edge is contained in a matching but $|\Gamma(A)|=|A|$ for some $A \subset X$ with $A \neq \emptyset, X$.

(iv) Suppose that every edge of $G$ is contained in a matching. Must every pair of independent edges in $G$ be contained in a matching? Give a proof or counterexample as appropriate.

[No form of Menger's Theorem or of the Max-Flow-Min-Cut Theorem may be assumed without proof.]