Hamilton út

A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.

Hamilton út létezésének szükséges feltétele:

Ha egy gráfból $k$ darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb $k+1$ darab komponense lehet.