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

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ if and only if $|N(U)|\ge |U|$ for every $U\subseteq L$. Here $N(U)$ is the set of vertices of $R$ adjacent to at least one member of $U$. Necessity follows because matched partners of $U$ are distinct members of $N(U)$.

For sufficiency induct on $|L|$; zero or one vertex is immediate. If a nonempty proper $U\subset L$ has $|N(U)|=|U|$, Hall's condition holds within the graph on $U,N(U)$. It also holds on the remaining classes: for $T\subseteq L\setminus U$,Induction gives matchings in these two disjoint subgraphs, and their union covers $L$. Otherwise every nonempty proper $U$ has $|N(U)|\ge |U|+1$. Choose any edge $lr$ and delete its two endpoints. Every nonempty subset of the remaining left class was a proper subset of $L$, so deleting $r$ leaves at least as many neighbours as vertices. Induction gives a matching there, and adjoining $lr$ completes the matching. This proves sufficiency in all cases.

Make a bipartite graph whose two classes index the two partitions, joining $i$ on the left to $j$ on the right exactly when $A_i\cap B_j\ne \varnothing$. For a subset $U$ of left indices, its union of blocks contains $2008|U|$ elements. They all lie in the blocks indexed by $N(U)$, whose union has $2008|N(U)|$ elements. Thus $|N(U)|\ge |U|$. Hall's theorem gives a matching covering all $n$ left vertices, hence also all $n$ right vertices. Its partner map is the required permutation $\pi$.

In the vertex form of Menger's theorem, for distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of pairwise internally vertex-disjoint $s$–$t$ paths equals the minimum size of an $s$–$t$ vertex separator. A separator is a subset of vertices other than $s,t$ whose deletion leaves no $s$–$t$ path; internally disjoint paths may share their endpoints but no other vertices. Equivalently, between disjoint vertex sets the maximum number of mutually vertex-disjoint connecting paths equals the minimum size of a separating vertex set, where endpoints may be deleted in that set version.

Add $s$ adjacent to every vertex of $V_1$ and $t$ adjacent to every vertex of $V_2$. Suppose an $s$–$t$ separator $C$ has fewer than $n$ vertices. It cannot contain all of either class. Choose $x\in V_1\setminus C$ and $y\in V_2\setminus C$. No edge can join the remaining two classes, since it would give a three-edge $s$–$t$ path. Hence every neighbour of $x$ lies in $C\cap V_2$, and every neighbour of $y$ lies in $C\cap V_1$. The minimum-degree bound impliesa contradiction. Menger's theorem therefore gives $n$ internally vertex-disjoint $s$–$t$ paths. Each uses at least one vertex of each original class, and only $n$ vertices are available in each class. Every path must consequently use exactly one of each. Their middle edges form a perfect matching.