Un grafo completo es un grafo simple en el todo vértice está conectado a todos los vértices restantes. Si a este grafo completo le damos dirección a sus enlaces obtendremos un grafo dirigido, al cual le llamaremos torneo.
Una trayectoria hamiltoniana es una trayectoria que pasa por todos los vértices del grafo. En 1934 Rédei probó un teorema básico sobre torneos y lo hizo usando un argumento de inducción.
Teorema. (Teorema de Rédei) Todo torneo tiene una trayectoria Hamiltoniana dirigida.
Demostración.
Usaremos inducción sobre el número de vértices.
Caso base: n=1 . El torneo trivial (sobre un vértice) tiene una trayectoria Hamiltoniana dirigida.
Paso inductivo. Supongamos ahora que n\geq 2 y que todo torneo sobre n-1 vértices tiene una trayectoria Hamiltoniana dirigida. Sea T un torneo sobre n vértices y sea v\in V(T). El digrafo T'=T-v es un torneo sobre n-1 vértices y por hipótesis de inducción tiene una trayectoria Hamiltoniana dirigida P'=v_1v_2..v_{n-1}.
Caso 1: (v, v_1) es un arco. En este caso la trayectoria Hamiltoniana buscada es T=v\cup T'
Caso 2: (v_{n-1}, v) es un arco. En este caso la trayectoria Hamiltoniana buscada es T= T'\cup v
Caso 3: (v_1, v) y (v, v_{n-1}) son arcos. En este caso existe un v_j tal que (v_j, v) y (v, v_{j+1}) son arcos. En tal caso la trayectoria T buscada sería T=v_1 v_2.. v_j v v_{j+1}..v_{n-1}.
De lo que se concluye la prueba.