# Mapping a round-robin tournament to prove one winning team can be selected?

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?

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