Pósa's theorem, ingraph theory, is asufficient condition for the existence of aHamiltonian cycle based on thedegrees of thevertices in an undirected graph. It implies two other degree-based sufficient conditions,Dirac's theorem on Hamiltonian cycles andOre's theorem. Unlike those conditions, it can be applied to graphs with a small number of low-degree vertices. It is named afterLajos Pósa, a protégé ofPaul 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\le d_2\le ...\le d_n,}$

then for each index the inequality 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.

• 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

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

• Theorems in graph theory

• Articles with short description
• Short description is different from Wikidata