# Using Hall's Marriage Theorem

Let $$k$$ and $$n$$ be two nonnegative integers with $$2k+1 \leq n$$. Let $$A$$ be the set of all $$k$$-subsets of $$\left\{1,2,\ldots,n\right\}$$. Let $$B$$ be the set of all $$\left(k+1\right)$$-subsets of $$\left\{1,2,\ldots,n\right\}$$. Consider the bipartite graph whose vertices are the elements of $$A \cup B$$; two vertices $$a \in A$$ and $$b \in B$$ are connected by an edge if $$a \subseteq b$$. I need to use Hall's Marriage theorem to show that this bipartite graph has a matching with $$\dbinom{n}{k}$$ edges.

I am very lost here I do not know where to start. I feel like multiplying the size of the sets by d will come into play but I am not sure. Any hints are greatly appreciated

• It follows pretty directly from Hall's Marriage Theorem. What have you tried, where are you stuck? Nov 22 '19 at 7:21
• Start by categorizing sets in $A$ and $B$ and their relation to one another. If a set in $A$ is $\{1,2,\cdots ,k\}$, then what are the sets in $B$ containing it? If a set in $B$ is $\{1,2,\cdots ,k+1\}$, what sets in $A$ are contained in it? Then devise a plan from here Nov 22 '19 at 9:44

First note that a set of $$A$$ is a subset of $$n-k$$ sets of $$B$$. Conversely, a set of $$B$$ contains $$k+1$$ sets of $$A$$.
Now consider $$M$$ sets of $$A$$. There are $$M(n-k)$$ edges to sets of $$B$$ and so these edges must connect to at least $$\frac{M(n-k)}{k+1}\ge M$$ distinct sets of $$B$$.
Therefore, by the Marriage Theorem, there is a matching for all $$\begin{pmatrix}n\\k\\\end{pmatrix}$$ sets of $$A$$.