We have seen that there is exactly one transitive tournament of each order. A tournament

Is it possible to have a round robin tournament involving six teams where three of the teams win three games and the other three teams win two games?

Is it possible to have a round robin tournament involving six teams where two teams win five games each, one team wins two games and the other three teams win one game each?

Is it possible to have a round robin tournament with more than three teams where each team wins the same number of games?

Give an example of two strong tournaments T and T of the same order that are not isomor- phic.

Show for every complete graph Kn (n 3) that there exists an orientation of Kn for which there are no directed cycles but the reversal of the direction of one of the edges results in a strong tournament.

Does there exist a transitive tournament of order 2?

We have seen that there is exactly one transitive tournament of each order. A tournament of order n 3 is defined to be circular if whenever (u, v) and (v,w) are arcs of T , then (w, u) is an arc of T . (a) How many circular tournaments of order 3 are there? (b) Show that in a tournament of order 3 or more, every vertex, with at most two exceptions, has positive outdegree and positive indegree. (c) How many circular tournaments of order 4 or more are there?

Does there exist a round robin tournament containing 2k teams, where k 3, in which k of these teams win r games and the remaining k teams win s games, where r 6= s?

A tournament T of order n 3 has the property that whenever (u, v) is an arc of T , then od u od v. Show that if T is Hamiltonian, then n is odd.

(a) Show that if an odd number of teams play in a round robin tournament, then it is possible for all teams to tie for first place. (b) Show that if an even number of teams play in a round robin tournament, then it is not possible for all teams to tie for first place.

Let u and v be distinct vertices in a tournament such that ~d(u, v) and ~d(v, u) are defined. Show that ~d(u, v) 6= ~d(v, u).

Prove that if u and v are vertices of a tournament such that ~d(u, v) = k, then id u k 1.

Prove that every Hamiltonian tournament is strong.

Let T be a tournament of order 3 or more. Prove that the length of a longest cycle in T equals the greatest order of a strong subdigraph in T .

(a) Find a Hamiltonian path in each tournament in Figure 15.20. (b) Find a Hamiltonian cycle in each strong tournament in Figure 15.20.

Prove that every vertex in a nontrivial strong tournament belongs to a directed triangle.

Let T be a tournament of order n 3 with V (T ) = {v1, v2, . . . , vn}. Prove that if od vi > id vi for 1 i n 1, then T is not strong.

Prove or disprove: (a) If every vertex of a tournament T belongs to a cycle in T , then T is strong. (b) For every pair u, v of vertices in a strong tournament T , there exists either a Hamiltonian u v path or Hamiltonian v u path. (c) If (u, v) is a directed edge of a strong tournament T , then (u, v) lies on Hamiltonian cycle of T .

Prove that if T is a tournament of order 4r with r 1, where 2r vertices of T have outdegree 2r and the other 2r vertices have outdegree 2r 1, then T is strong.

Let T be a tournament of order n. Prove that if every vertex of T has outdegree n1 2 or n1 2 , then T is strong.

Let T be a tournament of order n 4. Prove that if T contains two directed cycles C and C of order n 1 such that C contains a vertex not on C, then T is Hamiltonian.