Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / A / 1

Hall's marriage theorem says that a finite bipartite graph with parts $L,R$ has a matching covering $L$ if and only if $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because matching edges send the vertices of $S$ to distinct neighbours.

For sufficiency, choose a maximum matching $M$. If it misses $a\in L$, explore all alternating paths from $a$, taking unmatched edges from left to right and matched edges from right to left. Let $S\subseteq L$ and $T\subseteq R$ be the reached vertices. No vertex of $T$ can be unmatched, since flipping the edges along the resulting augmenting path would enlarge $M$.

Every neighbour of a reached left vertex is reached on the right: unmatched edges are exploration steps, and a matched edge leads back to an already reached matching partner. Thus $T=N(S)$. Each right vertex in $T$ is matched to a reached left vertex other than $a$, and every reached left vertex other than $a$ arose this way. These matching partners give a bijection $T\leftrightarrow S\setminus \{a\}$. Hence $|N(S)|=|S|-1$, contradicting the assumed inequality. Therefore the maximum matching covers $L$.

Write the bipartition as $L,R$. Counting edges by their left and right ends gives $2009|L|=2009|R|$, so the parts have equal size. Put $H=G-F$. If some $S\subseteq L$ violated Hall's marriage theorem in $H$, let $T=N_H(S)$, so $|T|\le |S|-1$.

There are $2009|S|$ edges of $G$ incident with $S$, of which at most $2009|T|$ can end in $T$. Thus at least $2009(|S|-|T|)\ge 2009$ end in $R\setminus T$. All those edges must have been deleted, by the definition of $T$. This contradicts $|F|=2008$. Hence $H$ has a matching covering $L$, and equal part sizes make it a perfect matching avoiding every edge of $F$.

False. The path graph on four vertices is bipartite and its first and last edges form a perfect matching. It has no cycle at all, so it has no Hamiltonian cycle. This counterexample is connected as well.

True. Every cycle in a bipartite graph has even length because its vertices alternate between the two parts. On a Hamiltonian cycle, choose every other edge. These edges are disjoint and cover every vertex exactly once, so they form a perfect matching.

False. The complete bipartite graph $K_{2009,2010}$ is $2009$-connected. Deleting fewer than $2009$ vertices leaves at least one vertex in each part and therefore a connected complete bipartite graph; deleting the smaller part disconnects the larger independent set. But its two parts have unequal sizes, so a matching cannot cover them both. Equivalently it has an odd number of vertices. Thus it has no perfect matching.