hinreichendes Kriterium dafür, daß ein Graph einen Hamiltonschen Kreis besitzt.

Im Jahre 1960 hat O. Ore folgendes nützliche Lemma präsentiert. Sind u und v zwei nicht adjazente Ecken eines Graphen G der Ordnung n mit

\begin{eqnarray}{d}_{G}(u)+{d}_{G}(\upsilon )\ge n,\end{eqnarray}

so ist G genau dann Hamiltonsch, wenn G + uv Hamiltonsch ist.

J.A. Bondy und V. Chvatal benutzten 1976 dieses Lemma von Ore als Grundlage für ihre Definition der sogenannten Hamiltonschen Hülle.

Es sei G ein Graph der Ordnung n. Bildet man ausgehend von G = G₁ eine längstmögliche Folge von Graphen (G_i)_i=1,2,…,p, indem man beim Übergang von G_i zu G_i+1 jeweils eine Kante k = uv hinzufügt, die zwei in G_i nicht adjazente Ecken u und v mit \({d}_{{G}_{i}}(u)+{d}_{{G}_{i}}(\upsilon )\ge n\) verbindet, so zeigten Bondy und Chvatal, daß G_p unabhängig von der Reihenfolge der hinzugefügten Kanten ist. Daher ist G_p ein wohldefinierter Graph, der den Namen Hamiltonsche Hülle trägt, in Zeichen

\begin{eqnarray}{G}_{p}=C{l}_{n}(G).\end{eqnarray}

Aus dem Lemma von Ore folgt nun sofort, daß G genau dann Hamiltonsch ist, wenn Cl_n(G) Hamiltonsch ist. Insbesondere besitzt G einen Hamiltonschen Kreis, wenn Cl_n(G) der vollständige Graph K_n ist, falls n ≥ 3 gilt.

Darüber hinaus haben Bondy und Chvátal auch für andere Eigenschaften von Graphen, wie z. B. k-facher Zusammenhang oder die Existenz eines k-Faktors, sogenannte Hüllenkonzepte entwickelt.