Pósa's theorem
Pósa's theorem, in graph theory, is a sufficient condition for the existence of a Hamiltonian cycle based on the degrees of the vertices in an undirected graph. It implies two other degree-based sufficient conditions, Dirac's theorem on Hamiltonian cycles and Ore's theorem. Unlike those conditions, it can be applied to graphs with a small number of low-degree vertices. It is named after Lajos Pósa, a protégé of Paul Erdős born in 1947, who discovered this theorem in 1962.
The Pósa condition for a finite undirected graph [math]\displaystyle{ G }[/math] having [math]\displaystyle{ n }[/math] vertices requires that, if the degrees of the [math]\displaystyle{ n }[/math] vertices in increasing order as
- [math]\displaystyle{ d_{1} \leq d_{2} \leq ... \leq d_{n}, }[/math]
then for each index [math]\displaystyle{ k \lt n/2 }[/math] the inequality [math]\displaystyle{ k \lt d_{k} }[/math] is satisfied.
Pósa's theorem states that if a finite undirected graph satisfies the Pósa condition, then that graph has a Hamiltonian cycle in it.
References
- "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl. 7: 225–226, 1962
- Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003, (Hungarian undergraduate level course book).
- Kronk, Hudson V. (1969), "Generalization of a theorem of Pósa", Proceedings of the American Mathematical Society 21: 77–78, doi:10.2307/2036861
- "Degree sequences forcing Hamilton cycles in directed graphs", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electron. Notes Discrete Math., 34, Amsterdam: Elsevier Sci. B. V., 2009, pp. 347–351, doi:10.1016/j.endm.2009.07.057
- Yin, Jian-Hua; Zhang, Yue (2011), "Pósa-condition and nowhere-zero 3-flows", Discrete Mathematics 311 (12): 897–907, doi:10.1016/j.disc.2011.02.023
External links
- Weisstein, Eric W.. "Pósa's Theorem". http://mathworld.wolfram.com/PosasTheorem.html.
- About the Pósa theorem
 |  |
