About Me

My photo
Ravi is an armchair futurist and an aspiring mad scientist. His mission is to create simplicity out of complexity and order out of chaos.

Sunday, November 18, 2012

Redei's theorem

Redei's theorem states that every tournament has a directed Hamilton path. We prove this theorem in this blog post.

Background


Tournament

A tournament is a complete graph with oriented edges.
It can be viewed as the result of a round-robin tournament, where every team plays every other team and there is always a winner and a loser in every match (no ties). The direction of each edge is from the winner to the loser of that match. In the above graph, team 1 beat team 2, hence the edge $1\rightarrow 2$ and so on.

Hamilton path

A Hamilton path is a path connecting all vertices of a graph (once and only once).
The directed path shown above in red is a Hamilton path, since it connects all vertices of the graph.

Now we are ready for the theorem and its proof.

Redei's theorem

Every tournament has a directed Hamilton path. This was first proven by Laszlo Redei in 1934.

Proof by induction

For the base case, consider a directed graph on 2 vertices, say $v_1\rightarrow v_2$. This is also a Hamilton path, since it covers both vertices. So the statement holds true for our base case.

For the inductive step, we assume that each tournament on $(n-1)$ vertices has a Hamilton path. Assume that this path is {$v_1,\cdots,v_{n-1}$} as shown in the graphs below. We consider 3 different scenarios for the new vertex $v$ added to this graph.

  1. In the first scenario, we have an edge $v\rightarrow v_1$ as shown by the red edge in the graph below. The new path $\{v,v_1,\cdots,v_{n-1}\}$ is a Hamilton path. So for this scenario, a tournament on $n$ vertices does have a Hamilton path.
  1. In the second scenario, we have an edge $v_{n-1}\rightarrow v$ as shown by the red edge in the graph below. The new path $\{v_1,\cdots,v_{n-1},v\}$ is a Hamilton path. So for this scenario too, a tournament on $n$ vertices does have a Hamilton path.
  1. In the final scenario different from the previous two, we have both $v_1\rightarrow v$ and $v\rightarrow v_{n-1}$ as shown in the graph below. In this case, the first vertex $v_i$ such that there is an edge $v\rightarrow v_i$ (shown as a dotted edge) completes a Hamilton cycle $\{v_1,\cdots,v_{i-1},v,v_{i+1},\cdots,v_{n-1}\}$. (Note that $i$ could be $n-1$ (the last vertex) if all edges preceding it go into $v$.) So for this scenario too, a tournament on $n$ vertices has a Hamilton path.

The above cover all the scenarios for the inductive step, completing an inductive proof of Redei's theorem that every tournament has a directed Hamilton path.

Conclusion

Using the analogy of matches in a round-robin tournament between $n$ teams, Redei's theorem says that it is always possible to find $n$ matches, such that team A beat team B, which beat team C and so on, which beat team N. Now that was not obvious before! (Note: team A doesn't mean team 1. $\{A, B, \cdots, N\}$ is some permutation of $\{1, 2, \cdots, n\}$.)

References

  1. Bondy, J.A., Murty, U.S.R., Graph Theory, 2008.

No comments:

Post a Comment