In a round-robin tournament each team plays every other team exactly once. If the teams ar...

In a round-robin tournament each team plays every other team exactly once. If the teams are labeled T1, T2, ..., Tn, 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 > 2, it is possible to label the teams T1, T2, ..., Tn so that Ti beats 7i+1 for all i = 1, 2, ..., n – 1. (For instance, one such labeling in the example above is T1 = A , T2 = B, T3 = C, T4 = E, T5 = D.) (Hint: Given k + 1 teams, pick one— say T'— and apply the inductive hypothesis to the remaining teams to obtain an ordering T1, T2, ..., Tk. Consider three cases: T' beats T1, T' loses to the first m teams (where 1 ≤ m ≤ k – 1) and beats the (m + 1)st team, and T' loses to all the other teams.)