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
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$.