Prove that every tournament contains a vertex u such that fo

Prove that every tournament contains a vertex u such that, for every other vertex x, there is a path from u to x of length at most 2.

Solution

Let u be the vertex which has maximum out degree in the tournament D

Consider

Nout(u) = {u1, u2, . . . , ur} and Nin(u) = {v1, v2, . . . , vs},where

r = outdeg(u) and s = indeg(u)

Since D is a tournament,

V (D) {u} = Nout(u) Nin(u) and Nout(u) Nin(v) = .

Hence clearly u is reachable to every vertex by a path of length 1.

Then for every vi (1 i s), there is some uj (1 j r) such that (uj , vi) is an arc in D; so that vi is reachable from u by a path of length 2, namely (u, uj , vi)

If not (ui,vj) is an arc for every j between 1 and r.

Nout(vi) {u1, u2, . . . , ur} {u}.

outdeg(vi) outdeg(u) + 1

Thus we get a contradiction to the maximality of outdeg(u). Hence, our assumption was false and thus proved