Directed 3- cycles in Tournaments

Directed 3- cycles in Tournaments

Recall that a tournament is a directed graph without parallel edges whose
underlying graph is K”. We showed in class:
Theorem. The number of transitive triples 9(0) in a tournament D of order
n is

[(0) = E Z od(v) (od(v) – 1).
vEV(D)

Corollary. The number of directed 3-cycles IS (3) – f(D).

1) Explain why the corollary IS true and why [(0) S (3) as a
consequence.

2) Explain the possible effects on f (D) of reversing the orientation of a
single edge 11!). Suppose before the switch that od(u) = a and
od(v) = b.

3) Suppose a tournament of order n has two teams who have beaten
n – 2 other teams. Must there be a directed 3-cycle in this situation?

4) Use the theorem and problem 2 to show that the only way for
f (D) = (g) is for the out-degrees to cover the entire set
{0.12, …,n – 1}.

5) Math/CSci 553 students should find recipes for tournaments that
maximize f(D) and tournaments that minimize f(D) as well, with
justifications.