A tournament is a directed graph obtained by choosing a direction for each edge in an undirected complete graph. For example, here is a tournament on 4 vertices:

Any tournament on a finite number $n$ of vertices contains a Hamiltonian path, i.e., directed path on all $n$ vertices. This is easily shown by induction on $n$: suppose that the statement holds for $n$, and consider any tournament $T$ on $n+1$ vertices. Choose a vertex $v_{0}$ of $T$ and consider a directed path $v_{1},v_{2},\ldots,v_{n}$ in $T\setminus\{v_{0}\}$. Now let $i\in\{0,\ldots,n\}$ be maximal such that $v_{j}\rightarrow v_{0}$ for all $j$ with $1\leq j\leq i$. Then

is a directed path as desired.

The name “tournament” originates from such a graph’s interpretation as the outcome of some sports competition in which every player encounters every other player exactly once, and in which no draws occur; let us say that an arrow points from the winner to the loser. A player who wins all games would naturally be the tournament’s winner. However, as the above example shows, there might not be such a player; a tournament for which there isn’t is called a $1$-paradoxical tournament. More generally, a tournament $T=(V,E)$ is called $k$-paradoxical if for every $k$-subset $V^{{\prime}}$ of $V$ there is a $v_{0}\in V\setminus V^{{\prime}}$ such that $v_{0}\rightarrow v$ for all $v\in V^{{\prime}}$. By means of the probabilistic method Erdős showed that if $|V|$ is sufficiently large, then almost every tournament on $V$ is $k$-paradoxical.

A transitive tournament is a tournament in which, for all vertices $v_{0}$, $v_{1}$ and $v_{2}$, if there is an edge from $v_{0}$ to $v_{1}$ and an edge from $v_{1}$ to $v_{2}$ then there is also an edge from $v_{0}$ to $v_{2}$.