This is a question on my Graph Theory homework, and I wanted some help in solving it:
If a tournament involving 2n teams has the following properties:
1.every day of the tournament involves n matches (with no teams repeated in a given day).
each team plays every other team exactly once during the tournament, for a total of 2n − 1 days.
there are no ties.
Show that it is possible to choose one winning team from each day of the tournament, with no team chosen more than once.
I tried to prove it through induction but keep getting stuck when I try to move beyond a base case.. Any idea how to build on this?
Let’s follow Alex’ hint. Consider a bipartite graph $G$ with bipartite sets $X$ and $Y$, where $X$ is the set of days and $Y$ is the set of teams. An edge between $x\in X$ and $y\in Y$ exists iff a team $x$ was a winner at a day $y$. We have to show that $G$ has an $X$-saturating matching. By Hall’s Marriage Theorem for this purpose we have to show that $|W|\le |N_G(W)|$ for every subset $W$ of $X$. Put $Z=Y\setminus N_G(W)$. Since none of teams of $Z$ was a winner in a day of $W$, all matches between teams of $Z$ were played at days of $X\setminus W$. Since each team of $Z$ played $|Z|-1$ such matches, $|Z|-1\le |X\setminus W|$. That is $|Y|-|N_G(W)|-1\le |X|-|W|$ and $|W|\le |N_G(W)|$.