This is all the textbook gives there is no more information

This is all the textbook gives, there is no more information

In a round-robin tournament each team plays every other team exactly once. If the teams are labeled T_1, T_2, ..., T_n, then the outcome of such a tournament can be represented by a drawing, called a directed graph, in which the teams are represented as dots and an arrow is drawn from one dot to another if, and only if, the team represented by the first dot beats the team represented by the second dot. For example, the directed graph below shows one outcome of a round-robin tournament involving five teams, A, B. C, D, and E. Use mathematical induction to show that in any round-robin tournament involving n teams, where n greaterthanorequalto 2, it is possible to label the teams T_1, T_2, ..., T_n so that T_i beats T_i + 1 for all i = 1, 2, ..., n - 1. (For instance, one such labeling in the example above is T_1 = A, T_2 = B, T_3 = C, T_4 = E, T_5 = D.)

Solution

Let n = 2. Then there was only one game played. Label the winner as T1 and loser as T2 and we are done.

Inductive Step:

Let k>=2. Assume that for all tournaments with k teams, there is a labelling as described above. Consider a tournament on k+1 teams. When we remove one team, say team A, we have a tournament on k teams.

Thus, by our inductive hypothesis, there is a labelling T1, T2, ..., Tk as above.

Either A beats team T1, A loses to the rest m teams (where 1<=m<=k-1) and beats the (m+1)st team, or A loses to all the other teams.

In the first case, A, T1, T2, ...., Tk is a desired ordering, so we relabel our teams so that A becomes T\'1, T1 becomes T\'2, and so on.

In the second case, T1, T2, ...., Tm, A, Tm+1, ...., Tk is a desired ordering (since A lost to Tm but beat Tm+1), and so we relabel accordingly.

In the third case, T1, T2, ..., Tk, A is a desired ordering (since A lost to everyone, in particular they lost to Tk), and so we relabel accordingly.

In all cases, we have found the desired labelling. Thus the result holds by mathematical induction.