Rédei's theorem (graph theory)

In graph theory , one of the branches of mathematics , Rédei's theorem is a theorem that is fundamental to the question of the passability of tournament graphs . The sentence goes back to a work by the Hungarian mathematician László Rédei from 1934.

Formulation of the sentence

The Rédeic sentence can be summarized as follows:

In a finite tournament with at least two nodes , the number of Hamiltonian orbits in it is always an odd number .

According to this, in every finite tournament there is at least one lane that contains every node exactly once.

Notes on the evidence

• The second part of Rédei's theorem above can easily be proved by means of complete induction .
• According to Horst Sachs , no simple proof is known for the theorem as a whole. In 1943 the Hungarian mathematician Tibor Szele (according to Sachs) delivered a very nice combinatorial proof .

literature

• Rudolf Halin : Graph theory (=  yields of research . Volume 138 ). tape I . Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).
• Dénes König : Theory of finite and infinite graphs . With a treatise by L. Euler. Ed .: H. Sachs (=  Teubner Archive for Mathematics . Volume 6 ). BSB BG Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 .
• L. Rédei : A combinatorial proposition . In: Acta Scientiarum Mathematicarum ; formerly: Acta Litterarum ac Scientiarum (Sectio Scientiarum Mathematicarum), Szeged . tape 7 , 1934, pp. 39-43 ( acta.fyx.hu ).
• Horst Sachs: Introduction to the theory of finite graphs . Carl Hanser Verlag, Munich 1971, ISBN 3-446-11463-7 . MR0345857
• T. Szele : Combinatorial Studies on Directed Complete Graphs . In: Publicationes Mathematicae Debrecen . tape 13 , 1966, pp. 145-168 ( math.klte.hu ). MR0207591

References and footnotes

1. ↑ ^{a b} Rudolf Halin: Graphentheorie I. 1980, pp. 205 ff., 220-221
2. ↑ Dénes König: Theory of finite and infinite graphs. 1986, pp. 29-31
3. ↑ ^{a b} Horst Sachs: Introduction to the theory of finite graphs. 1971, pp. 164-166
4. ↑ Horst Sachs (op. Cit., P. 165) describes such a Hamiltonian orbit as a complete orbit .
5. ↑ Publicationes Mathematicae Debrecen , Volume 13, 1966, pp. 145 ff.