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

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

then for each index $k<n/2$ the inequality $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[edit]

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: 77–78, doi:10.2307/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