A roundrobin tennis tournament involves players p1 p2 pn

A round-robin tennis tournament involves players p1, p2, . . . , pn and every pair plays a match. Prove
that, for every n 2 and no matter how the matches turn out, it is always possible to line up the players
so that every player beats the person behind them but loses to the person in front of them.
Example: Recall graphs for representing relationships. We can represent the round-robin tournament
with a graph and an arrow from pi to pj means that pi beats pj .

I know how to show this by example for any case, but how does one construct this into a general proof? Thanks

Solution

Let there exists a ranking p1, p2, . . . , pn of the players such that pi defeats pi+1 for all i = 1, . . . , n1.

Base case n = 0, there are no players, so there is nothing to prove. Therefore P(0) trivially holds.

Inductive step: Let such a ranking exists for every tournament with up to r 0 players in order to prove that such a ranking exists in a tournament with r + 1 players. Now, let us choose an arbitrary player x. Let B(x) be the set of players that beat x and let L(x) be the set of players that lose to x. Now we have that any of these sets have at most r players and that either might be empty. Let b = |B(x)|. Then 0 b r and by the induction hypothesis, there exists a ranking of the players in B(x), say p1, . . . , pb such that pi defeats pi+1 for all i {1, . . . , b 1}. Similarly, as 0 |A(x)| = (r + 1) 1 b = r b r, there exists a ranking of the players in B(x), say pb+2, . . . , pk+1 such that pi defeats pi+1, for all i {b + 2, . . . , k}

Set pb+1 = x. Then p1, . . . , pb, pb+1, pb+2, . . . , pr+1 is a ranking of all the players. By construction, pi defeats pi+1. whenever i 6= b, b + 1. In addition, we know that pb defeats x = pb+1 since pb B(x) and that x = pb+1 defeats pb+2 since pb+2 L(x). Thus, p1, . . . , pb, pb+1, pb+2, . . . , pr+1 is the desired ranking