Pósa's theorem

Template:Short description Template:Distinguish 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\le d_2\le ...\le 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

• Template:Citation
• Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003, (Hungarian undergraduate level course book).
• Template:Citation
• Template:Citation
• Template:Citation

External links

• Template:Mathworld
• About the Pósa theorem