Skip to main content
1 of 4

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. Form a hypergraph $H$ as follows: the vertex set of $H$ consists of those pairs $(x,y)$ such that $x \in X$, $y \in Y$, and $xy \in V(G)$. For each $y_0 \in Y$, we have a hyperedge $\{(x,y_0) : x \in N_G(y_0)\}$.

Letting $H_i$ be the hypergraph consisting of all vertices $(x_i, y)$ for $y \in N_G(x_i)$, and letting $\mathcal{A} = \{H_1, \ldots, H_n\}$, we see that $(H_1, \ldots, H_n)$ has a system of disjoint representatives if and only if $G$ has a perfect matching. The condition of Aharoni and Haxell's Theorem 1.1 ("for every subfamily $\mathcal{B}$ of $\mathcal{A}$ there exists a matching $M_{\mathcal{B}}$ in $\bigcup \mathcal{B}$ which cannot be pinned by fewer than $|\mathcal{B}|$ disjoint edges from $\mathcal{B}$") is then seen to be equivalent Hall's Condition for $G$.