Extending $k$-element subsets of an $n$-element set to $k+1$ element subsets

Question

The question is as follows:

Let $k,n$ be positive integers such that $k < n/2.$ Prove that all $k$-element subsets of an $n$-element set can be extended to all $k+1$ element subsets of the same $n$-element set such that all $k+1$ element subsets obtained as extensions are distinct.

The question was given as a graph theory question, but I cannot understand it at all. Any help is appreciated.

Answer 1

My graph theory skills are quite rusted, but I would try the following:

Consider the bipartite graph consisting of the $k$-element subsets in one partition and the $k+1$-element subsets in the other partition. Draw an edge, if and only if the $k$-subset is contained in the $k+1$-subset. The question now becomes „does this graph admit a matching?“ (by which I mean a subset of pairwise nonadjacent edges covering the $k$-subsets). I recall vaguely that there are theorems about such matchings of bipartite graphs, but I don’t know their names any more, unfortunately.

I hope this will be helpful in some way, at least as starting point.

Answer 2

Let $S_m$ be a set of all $m$ element subsets of $n$ element set.

So you are basicly searching for an injective mapping from $f:S_{k}\to S_{k+1}$ such that $X\subset f(X)$.

We need Hall marriage theorem here.

Connect a set $X\in S_k$ with $Y\in S_{k+1}$ iff $X\subset Y$. Then $\deg(X) = n-k$ and $\deg(Y) = {k+1\choose k} =k+1$.

Now check if the marriage condition is fullfiled. Take an arbitrary $S\subset S_k$ and let $E$ be the set of all edges from $S$ and $E'$ the set of all edges from $N(S)$. Then we have $E\subseteq E'$ so $|E|\leq |E'|$. Now $$|E| = |S|(n-k)\;\;\;\;\wedge \;\;\;\;|E'| = |N(S)|(k+1)$$ so $$|N(S)| \geq |S|\cdot {n-k\over k+1}\geq |S|$$ and we are done.