I am trying to prove or disprove the following Lemma:


Let $S=[n]$ and $\mathcal{T}$ be the set of all $k$-subsets of $S$ that contain $t \in [n]$. Furthermore, let $\mathcal{R}$ be the set of all $k$-subsets of $S$ that do no contain $t$.



> 
> Is it possible to choose $|\mathcal{R}|$ elements from $\mathcal{T}$ denoted as $T\_1, \dots, T\_{|\mathcal{R}|}$ and an ordered tuple $u = (u\_1, \dots, u\_{|\mathcal{R}|})$ with $u\_i \in S \setminus T\_i$ for all $i \in [|\mathcal{R}|]$ such that $\bigcup\_{i=1}^{|\mathcal{R}|} \{(T\_i \setminus \{t\}) \cup \{u\_i\} \} = \mathcal{R}$.
> 
> 
> 


I don't know whether or not it is true but after trying some examples it seems to be true, e.g., for $n=5$, $k=3$ and $t=3$. I can recover $\mathcal{R}$ from $\{1, 3, 4\}$, $\{1, 3, 5\}$, $\{2, 3, 4\}$, $\{1, 3, 5\}$ by picking the sequence $(2,4,5,2)$. Would it be hard to formally prove this?



Recovering set of $k$-subsets without specific element $t$ by modifying subsets with element $t$
I assume what is meant is whether it is always possible to choose a size $|\mathcal R|$ subcollection $\mathcal U$ of $\mathcal T$ and elements $e\_U \notin U$ for each $U \in \mathcal U$ such that $\{(U \setminus \{t\}) \cup \{e\_U\} \mid U \in \mathcal U\}$ is equal to $\mathcal R$. I claim that the answer is **yes**, provided that $k \geq n-k$. Note that $k \geq n-k$ is necessary since $|\mathcal T|=\binom{n-1}{k-1}$ and $|\mathcal R|=\binom{n-1}{k}$, so we require $\binom{n-1}{k-1} \geq \binom{n-1}{k}$.


Here is the proof. Let $G$ be the bipartite graph where the sets in $\mathcal R$ are the vertices on the left and the sets in $\mathcal T$ are the vertices on the right. Make $R \in \mathcal R$ adjacent to $T \in \mathcal T$ if and only if $T \setminus \{t\} \subseteq R$. Note that every vertex on the left has degree $k$ and every vertex on the right has degree $n-k$. Since $k \geq n-k$, by Hall's theorem, there is a matching in $G$ covering all the vertices on the left. This matching gives the required subcollection $\mathcal U$ of $\mathcal T$ and the elements $e\_U$.


