Pósa's theorem
id:
p-sa-s-theorem-25-38627
title:
Pósa's theorem
text:
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
brand slug:
wiki
category slug:
encyclopedia
description:
Sufficient condition for a Hamiltonian cycle in a graph, based on its vertex's degrees
original url:
https://en.wikipedia.org/wiki/P%C3%B3sa%27s_theorem
date created:
date modified:
2023-12-03T02:30:37Z
main entity:
{"identifier":"Q1243386","url":"https://www.wikidata.org/entity/Q1243386"}
image:
fields total:
13
integrity:
14