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

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because the distinct matched partners of $S$ belong to $N(S)$.

For sufficiency take a maximum matching. If it leaves $x\in L$ unmatched, explore alternating paths starting at $x$, traversing unmatched edges from left to right and matched edges back to the left. No reached right vertex can be unmatched, since flipping the edges of such an alternating path would augment the matching. Let $S,T$ be the reached left and right sets. Every neighbour of $S$ lies in $T$: unmatched edges are explored, and a matched edge from a reached left vertex leads to its already reached predecessor. Conversely every member of $T$ is a neighbour of $S$. Their matched partners are exactly $S\setminus \{x\}$, so $|N(S)|=|T|=|S|-1$, contradicting the hypothesis. Thus a matching covering $L$ exists.

If no complete matching exists, Hall's theorem gives a nonempty $S\subseteq V_1$, of size $k$, with $|N(S)|\le k-1$. The pairs between $S$ and $V_2\setminus N(S)$ must be nonedges, so there are at leastmissing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore a complete matching exists.

The strictness is necessary: isolate one vertex of $V_1$ and put all edges between the remaining $n-1$ left vertices and all $n$ right vertices. There are exactly $n(n-1)$ edges and no matching can cover the isolated vertex. This also handles $n=1$.

First the graph is connected: every component has at least $\delta (G)+1>n/2$ vertices, so two components cannot fit. Take a longest path $v_1,\dots ,v_k$. Every neighbour of either endpoint lies on that path. In the index set $\{1,\dots ,k-1\}$ defineTheir sizes sum to $d(v_1)+d(v_k)\ge n>k-1$, so they share an index $i$. The edges at that index give the cyclecontaining every vertex of the path. The minimum-degree assumption and $n\ge 3$ ensure the resulting cycle is nondegenerate. If it omitted any graph vertex, connectedness would supply an edge from outside it to the cycle. Starting with that outside vertex and then following the cycle without closing it gives a path with $k+1$ vertices, contradicting maximality. Thus the cycle is Hamiltonian. This proves Dirac's theorem in the required case.