# Proving Hall's marriage theorem using Sperner's lemma

In the paper Hall's theorem for hypergraphs (Aharoni and Haxell, 2000), the authors prove a theorem on the existence of perfect matchings in bipartite hypergraphs, using Sperner's lemma. At the last page (6), they say that "we have here a topological proof of Hall's theorem" (for bipartite graphs). I thought it should be easy to write this proof explicitly, since a simple bipartite graph is just a bipartite hypergraph in which each hyperedge is of size 2. But there is a problem: during the proof, the authors assume that the sets of neighbors (i.e., the sets $$N(x)$$ for each vertex $$x\in X$$, where $$X$$ is one part of the hypergraph) are pairwise-disjoint. For a hypergraph, this assumption is without loss of generality, since we can add dummy vertices to edges, and this does not affect the theorem conditions or concludion. But in a graph, we cannot add vertices to edges.

So my question is: is there an explicitly-written proof of Hall's marriage theorem, using Sperner's lemma (or a similar topological theorem)?

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\}$$. For each $$i$$, define a $$1$$-uniform hypergraph $$H_i$$ with vertex set $$N(x_i)$$ and edge set $$\{ \{y\} : y \in N(x_i) \}$$.
Letting $$\mathcal{A} = \{H_1, \ldots, H_n\}$$, we see that $$\mathcal{A}$$ has a disjoint set of representatives if and only if $$G$$ has a matching that saturates $$X$$. Now the condition of Aharoni and Haxell's Theorem 1.1 applied to the family $$\mathcal{A}$$ is clearly equivalent to Hall's Condition on $$G$$. Since classical Hall's Theorem falls out of the hypergraph version so quickly, I think it's fair to think of the topological proof of the hypergraph version as also being a topological proof of Hall's theorem.