Problem
COM-B2-M04-P019 A King in a Tournament
Prove that in every tournament there is a vertex \(v\) from which every other vertex can be reached by a directed path of length at most \(2\).
Choose a vertex with the maximum number of outgoing edges.
Choose a vertex \(v\) with maximum outdegree. Let \(u\) be a vertex not reached by an edge from \(v\). Then in the tournament we must have \(u\to v\).
Suppose no out-neighbour \(w\) of \(v\) has an edge \(w\to u\). Then for every such \(w\), the edge is directed \(u\to w\). Also \(u\to v\). Hence \(u\) defeats everyone defeated by \(v\), and also defeats \(v\) itself. Thus \(u\) has larger outdegree than \(v\), a contradiction.
Therefore there is an out-neighbour \(w\) of \(v\) such that \(w\to u\). Then \(v\to w\to u\). Vertices directly defeated by \(v\) are reached in one step. Hence \(v\) reaches every vertex in at most two steps.
The problem is strong because the extremal choice is not a longest path; one must choose maximum outdegree.