The Tournament Theorem of Rédei Revisited

Basic Information

• Paper ID: 2510.10659
• Title: The Tournament Theorem of Rédei Revisited
• Authors: Thomas Schweser (Technische Hochschule Rosenheim), Michael Stiebitz (Technische Universität Ilmenau), Bjarne Toft (University of Southern Denmark)
• Classification: math.CO (Combinatorics)
• Submission Date: October 12, 2025 to arXiv
• Paper Link: https://arxiv.org/abs/2510.10659

Abstract

In 1934, L. Rédei published a famous theorem: the number of Hamiltonian paths in a tournament is odd. In fact, this is a corollary of a stronger theorem in his paper. In the early 1970s, G.A. Dirac obtained a stronger theorem in his lectures at Aarhus University, and C. Berge presented another stronger version in his monograph on graphs and hypergraphs. This paper presents the stronger theorems of Rédei, Dirac, and Berge, and explains the connections between them. Dirac's stronger theorem has two corollaries, one equivalent to Rédei's stronger theorem and another related to Berge's stronger theorem.

Research Background and Motivation

Problem Description

This paper revisits a classical result in graph theory—Rédei's theorem. The theorem states that any tournament has an odd number of Hamiltonian paths. However, this famous conclusion is actually only a special case of a deeper theoretical result.

Research Significance

1. Historical Value: Rédei's theorem is a milestone result in combinatorics; understanding its deeper theoretical foundations is of great importance
2. Theoretical Unification: By comparing the approaches of different mathematicians, the paper reveals deep connections between seemingly independent results
3. Methodological Contribution: It demonstrates how to derive classical results from more general theoretical frameworks

Existing Limitations

Although Rédei's original theorem is well-known, its stronger versions and connections with the work of other mathematicians have not been adequately recognized and systematically organized.

Research Motivation

The authors discovered these connections while writing "Milestones in Graph Theory" and aim to systematically present and prove these stronger theorems and their interrelationships.

Core Contributions

1. Systematic Presentation: The first systematic presentation of the stronger theorems on Hamiltonian paths by Rédei, Dirac, and Berge
2. Theoretical Connections: Establishes equivalence and implication relationships between these seemingly independent results
3. Unified Framework: Provides a unified theoretical framework through Dirac's stronger theorem
4. New Combinatorial Results: Proposes the Berge-Dirac theorem as a combination of two strong results

Detailed Methodology

Basic Concept Definitions

Mixed Graph: A graph structure where each pair of vertices can be one of: a non-edge, an undirected edge, or a directed edge.

Permutation Representation: For a mixed graph G with n vertices, a permutation x is defined as an ordering of vertices: $x = (x_1, x_2, \ldots, x_i, x_{i+1}, \ldots, x_n)$

Edge Set Classification:

• $E_1$: Set of non-edges
• $E_2$: Set of undirected edges
• $E_3$: Set of directed edges
• $\overline{E_3}$: Set of all edges in $E_3$ with reversed directions

Core Theorem Framework

Dirac's Stronger Theorem (Theorem 2.1)

Let G be a mixed graph with at least 2 vertices, and let A be a subset of $E_1 \cup E_2$. Define:

• $N_A$: The number of permutations containing all elements of A and no elements of $\overline{E_3}$
• $N_{=A}$: The number of permutations containing exactly A as their elements from $E_1 \cup E_2$ and no elements of $\overline{E_3}$

Then $N_A$ and $N_{=A}$ have the same parity; in particular, $N_A - N_{=A}$ is even.

Proof Techniques

Key Lemma (Lemma 2.2)

Let A be a subset of $E_1 \cup E_2$, D be a subset of $E_3$, and N be the number of permutations containing all elements of $A \cup D$. Then N is even, unless:

• $|A| + |D| = n - 1$
• $|D| \geq 1$
• $A \cup D = E(x)$ for some permutation $x \in P(G)$

In the exceptional case, $N = 1$.

Proof Strategy

Using the inclusion-exclusion principle and parity analysis: $N_A = \sum_{D \subseteq E_3, |D| \leq n-1-|A|} (-1)^{|D|} M(D)$

Through modulo 2 arithmetic, we prove that $N_A \equiv N_{=A} \pmod{2}$.

Equivalence Proofs Between Theorems

Equivalence of Rédei's Stronger Theorem

A constructive proof demonstrates the equivalence between Dirac's Corollary 3 and Rédei's stronger theorem:

1. Forward Direction: Deriving Rédei's stronger theorem from Dirac's Corollary 3
2. Reverse Direction: Constructing a proof of Dirac's Corollary 3 from Rédei's stronger theorem

Main Theoretical Results

Rédei's Stronger Theorem (Theorem 1.1)

Let T be a tournament with at least 2 vertices. Add to T a non-empty set of new vertices W and some undirected edges between W and T as well as within W. Then the number of Hamiltonian paths in the new graph with both endpoints in T is even.

Berge's Stronger Theorem (Theorem 1.2)

Let G be a mixed graph with at least 2 vertices, and let $\overline{G}$ be its complement. Then the number of Hamiltonian paths in G and $\overline{G}$ have the same parity.

Dirac's Corollaries

1. Corollary 1: In a complete mixed graph, the number of Hamiltonian paths containing at least one undirected edge is even
2. Corollary 2: The difference in the number of permutations of a specific type is even
3. Corollary 3: Equivalent to Rédei's stronger theorem

Berge-Dirac Theorem (Theorem 4.1)

For a mixed graph G, define:

• $P_0$: Set of permutations not containing elements of $\overline{E_3}$
• $P_i$: Set of permutations not containing elements of $E_i \cup \overline{E_3}$ ($i \in \{1,2\}$)
• $P_3 = P_1 \cap P_2$

Then $|P_0| + |P_1| + |P_2| + |P_3|$ is even.

Analysis of Theoretical Connections

Equivalence Relations

• Dirac's Corollary 3 ⟺ Rédei's Stronger Theorem
• In the complete graph case: Dirac's Corollary 2 ⟺ Berge's Stronger Theorem

Implication Relations

• Dirac's Stronger Theorem → Dirac's Corollaries 1, 2, 3
• Dirac's Corollary 2 + Berge's Stronger Theorem → Berge-Dirac Theorem
• Berge-Dirac Theorem → Dirac's Corollary 2 ⟺ Berge's Stronger Theorem

Related Work

Historical Development

1. 1934: Rédei publishes the original theorem and its stronger version
2. Early 1970s: Dirac independently discovers stronger results in lectures at Aarhus University
3. 1970: Berge presents another stronger version in his monograph on graphs and hypergraphs
4. 2025: This paper systematically organizes the connections between these results

Method Comparison

• Rédei's Method: Based on edge reversal techniques in tournaments
• Dirac's Method: Uses permutations and the inclusion-exclusion principle
• Berge's Method: Analyzes symmetry through the complement graph

Conclusions and Discussion

Main Conclusions

1. Establishes systematic connections between three seemingly independent stronger theorems
2. Dirac's method provides the most general framework
3. The classical Rédei theorem is a special case of these deeper results

Theoretical Significance

This paper not only clarifies the relationships between historically important results but also demonstrates how to unify different approaches through a more general theoretical framework.

Future Directions

1. Explore applications of these techniques to other combinatorial structures
2. Seek more concise proofs of the Berge-Dirac theorem
3. Investigate generalizations to broader classes of graphs

In-Depth Evaluation

Strengths

1. Historical Value: Systematically organizes important historical results and their connections
2. Theoretical Depth: Provides a unified theoretical framework for understanding different approaches
3. Rigorous Proofs: Restates and proves classical results using modern mathematical language
4. Pedagogical Value: Clearly demonstrates the historical development and interconnections of mathematical ideas

Technical Contributions

1. Method Unification: Unified treatment of different types of paths through the concept of permutations
2. Proof Techniques: Clever use of the inclusion-exclusion principle and parity analysis
3. Constructive Proofs: Provides constructive proofs of equivalence between theorems

Limitations

1. Scope of Application: Primarily theoretical results with limited practical applications
2. Computational Complexity: Does not discuss the computational complexity of related algorithms
3. Generalizability: Generalizations to broader graph classes remain to be explored

Impact Assessment

1. Theoretical Impact: Provides new perspectives for understanding classical results in combinatorics
2. Educational Value: Suitable as teaching material for advanced graph theory courses
3. Research Inspiration: May inspire the search for similar unified frameworks in other combinatorial structures

References

1 L.W. Beineke, B. Toft, R.J. Wilson, Milestones in Graph Theory. A Century of Progress, MMA Press Spectrum Vol. 108 (2025).

2 C. Berge, Graphes et hypergraphes, Dunod 1970.

3 G. A. Dirac, Handwritten notes, Aarhus University 1970s.

4 L. Rédei, Ein kombinatorisher Satz, Acta Sci. Math. (Szeged) 7 (1934), 39–43.