Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / R (Graph Theory)

Use the equivalent bipartite formulation: the left set has $m$ vertices and a matching must cover it. Necessity is immediate, since distinct matched partners for any left subset must all lie in its neighborhood.

For sufficiency, induct on $m$. The cases zero and one are immediate from the neighborhood condition. If a nonempty proper left subset $A$ satisfies $|N(A)|=|A|$, induction matches $A$ into $N(A)$. For the remaining left vertices and remaining right vertices, any subset $B$ has at least $|B|$ available neighbors: applying Hall's inequality to $A\cup B$ and removing the $|A|$ possible neighbors in $N(A)$ proves this. Induction supplies the second matching, and the two combine.

If no nonempty proper subset has equality, all such subsets have at least one extra neighbor. Choose any left vertex and one of its neighbors and match them. After deleting the pair, each nonempty subset of the remaining left side originally was proper and had at least $|B|+1$ neighbors; losing the chosen right vertex leaves at least $|B|$. Induction completes the matching. Thusis sufficient as well as necessary. If the right set is infinite, any subset with infinitely many neighbors automatically meets the finite inequalities, and the same finite-left induction applies.

A complete matching from $V_1$ to $V_2$ is a set of edges with no shared endpoints that contains an edge incident to every vertex of $V_1$. The theorem in (i) gives the necessary and sufficient conditionThe intended setting is a finite left vertex set; no condition that every vertex of $V_2$ be used is imposed.

Form a bipartite graph with left labels $1,\dots ,m$, right set $E$, and an edge $i-e$ exactly when $e\in S_i$. A matching covering all left labels is precisely a choice of distinct representatives. Its neighborhood condition isThus this is necessary and sufficient. The underlying set $E$ may be infinite; only the number of sets to be represented is finite.

The missing sets in the five columns are $\{4,5\}$, $\{1,3\}$, $\{4,5\}$, $\{2,3\}$ and $\{1,2\}$. One choice of distinct representatives is $(4,1,5,3,2)$, giving the fourth row. Each column then has exactly one missing number, producing the fifth row $(5,3,4,2,1)$. A completed square isEvery row and column contains each number from one to five once. The construction explicitly chooses from the missing sets, so it preserves all entries of the given rectangle.

For an $m\times n$ rectangle, let $S_j$ be the symbols absent from column $j$. Each has size $n-m$. Across all columns, each symbol is absent exactly $n-m$ times, because it appears once in each existing row. For any set $J$ of columns, count incidences between those columns and their missing symbols. There are $|J|(n-m)$ incidences, while each distinct symbol in the union contributes at most $n-m$. Therefore $|{\bigcup }_{j\in J}{S}_j|\ge |J|$.

Hall's theorem supplies distinct representatives, one per column, forming an additional row with all $n$ symbols. This extends the rectangle without any column repetition. Repeat with $m+1$ rows, then successively until there are $n$ rows. Hence every finite latin rectangle extends to a Latin square by adding the required rows.