Misplaced Pages

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 ${\displaystyle G}$ having ${\displaystyle n}$ vertices requires that, if the degrees of the ${\displaystyle n}$ vertices in increasing order as

${\displaystyle d_{1}\leq d_{2}\leq ...\leq d_{n},}$

then for each index ${\displaystyle k<n/2}$ the inequality ${\displaystyle k<d_{k}}$ 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

• Pósa, L. (1962), "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876
• 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 (1): 77–78, doi:10.2307/2036861, JSTOR 2036861, MR 0237377
• Kühn, Daniela; Osthus, Deryk; Treglown, Andrew (2009), "Degree sequences forcing Hamilton cycles in directed graphs", European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electron. Notes Discrete Math., vol. 34, Amsterdam: Elsevier Sci. B. V., pp. 347–351, doi:10.1016/j.endm.2009.07.057, MR 2591466
• 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, MR 2787300

External links

• Weisstein, Eric W., "Pósa's Theorem", MathWorld
• About the Pósa theorem

• Graph theory
• Mathematical theorems