Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 17J (Graph Theory)

A matching from $X$ to $Y$ consists of disjoint edges saturating every vertex of $X$. The criterion is Hall marriage theorem.

For sufficiency, induct on $|X|$. If a nonempty proper $S\subset X$ is tight, $|N(S)|=|S|$, apply induction to $S,N(S)$ and to the graph left after deleting them. If no proper set is tight, choose any edge $xy$, delete its endpoints, and Hall still holds because every nonempty proper subset formerly had at least one spare neighbour. Induction completes the matching. Necessity is immediate.

For $S\subseteq X$, count with reciprocal degrees. On every edge $xy$, $d(x)\ge d(y)$, soHall's condition holds, so Hall marriage theorem supplies the matching.

Assume no deletion works. For each $x\in A_i$, some $A_j$ contains $A_i\setminus \{x\}$; otherwise deleting $x$ preserves the antichain. For different deleted elements these witnesses are distinct, since one witness containing both complements would contain $A_i$. Thus every element of $A_i$ belongs to at least $|A_i|$ sets.

Use the incidence graph with left class ${\bigcup }_i{A}_i$ and right class $\{A_i\}$. Along every incidence edge, the degree of the element is at least the degree $|A_i|$ of the set vertex. Part (b) gives a matching from the union into the $k$ sets, forcing $|{\bigcup }_i{A}_i|\le k$, a contradiction.