3
$\begingroup$

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

  1. each team plays every other team exactly once during the tournament, for a total of 2n − 1 days.

  2. 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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.