Let $K_n$ be partitioned into $n−1$ perfect matchings. We have $n$ teams in a soccer match: on each of $n − 1$ days, $n$ teams pair up according to the day’s perfect matching, i.e. each of the $\frac n 2$ edges tells who would play whom on that day. On each of the $n − 1$ days, there are $\frac n 2$ winning teams from the $\frac n 2$ games. So, there are $\frac n 2$ winners on Day 1, $\frac n 2$ winners on Day 2, ..., and $\frac n 2$ winners on Day $(n − 1)$.
Prove that no matter how the $\binom n 2$ individual games turned out, it is always possible to select one team who was a winner on Day 1, one team who was a winner on Day 2, ..., and one team who was a winner on Day $(n−1)$, such that we don’t pick the same team twice.
I understand the proof that $K_n$ can be partitioned into $n−1$ perfect matchings. Is the proof helpful in any way to this problem? I am not sure where to start.
Consider an auxiliary bipartite graph $G$ defined as follows. One of partite set of $G$ is the set $V$ of vertices of $K_n$ and the other is the set $D$ of days. There exists an edge between a vertex $v$ and a day $d$ provided a team $v$ is a winner of the day $d$. Then we have to show that there exists a $D$-saturating matching on $G$, that is a matching covering each vertex in $D$. By Hall marriage theorem this holds iff $|W|\le |N_G(W)|$ for any subset $W$ of $D$. Let’s show that the latter condition is satisfied. Let $W$ be any non-empty subset of $D$. Then $V\setminus N_G(W)$ is the set of vertices $v$ of $K_n$ such that $v$ is not a winner of any day $d\in D$. Pick any such $v$. Let $V_v=\{u\in V: u$ wins $v$ at some day of $D\}$. Then $|V_v|=|W|$ and $V_v\subset N_G(W)$.