A tournament is a directed graph in which every pair of vertices has exactly one edge between them ( ...

---

A tournament is a directed graph in which every pair of vertices has exactly one edge between them (in one direction). The name comes from thinking of the graph as a competition: if the edge between x and y is directed towards y, then x beat y in their match. Prove that any n-vertex tournament contains a vertex of out-degree at least (n - 1)/2.