ein Graph G, der einen Kreis C besitzt, welcher alle Ecken des Graphen enthält, für den also E(C) = E(G) gilt. Dieser Kreis C wird dann Hamiltonscher Kreis genannt.

Ein Weg W eines Graphen G mit E(W) = E(G) heißt Hamiltonscher Weg. Ist jedes Eckenpaar eines Graphen G durch einen Hamiltonschen Weg verbunden, so spricht man von einem Hamilton-zusammenhängenden Graphen. Aus diesen Definitionen folgt unmittelbar, daß ein Hamilton-zusammenhängender Graph Hamiltonsch ist, und ein Hamiltonscher Graph einen Hamiltonschen Weg besitzt.

Obwohl die Definitionen für Eulersche (Eulerscher Graph) und Hamiltonsche Graphen gewisse Ähnlichkeiten aufweisen, sind die zu untersuchenden Probleme von völlig unterschiedlicher Schwierigkeit. Während durch den Satz von Euler-Hierholzer ein einfaches notwendiges und hinreichendes Kriterium für Eulersche Graphen zur Verfügung steht, ist bisher für Hamiltonsche Graphen keine befriedigende Charakterisierung gelungen. Der Grund hierfür ist, daß das Erkennen Hamiltonscher Graphen zu den Prototypen der NP-vollständigen Probleme gezählt werden kann.

Es sind aber eine Fülle von hinreichenden Bedingungen bekannt, wobei die älteste von G.A. Dirac (1952) stammt.

Ein Graph G mit mindestens drei Ecken ist Hamiltonsch, wenn \begin{eqnarray}2\delta(G)\geq \vert E(G)\vert\end{eqnarray}gilt, wobei δ(G) der Minimalgrad von G ist.

Der nächste Satz von Ore (1960), der sofort aus dem Lemma von Ore folgt, verbessert das Resultat von Dirac.

Ist G ein Graph mit |E(G)| ≥ 3, und gilt für alle nicht adjazenten Ecken x, y die Ungleichung \begin{eqnarray}d_{G}(x)+d_{G}(y)\geq \vert E(G)\vert,\end{eqnarray}so ist G Hamiltonsch.

Darüber hinaus hat Ore 1963 gezeigt, daß G sogar Hamilton-zusammenhängend ist, wenn für alle nicht adjazenten Ecken x, y die etwas stärkere Bedingung \begin{eqnarray}d_{G}(x)+d_{G}(y)\geq \vert E(G)\vert+1\end{eqnarray} erfüllt ist.

<?PageNum _364Von den etwas neueren Ergebnissen sei noch eine Verallgemeinerung des Satzes von Ore genannt, die auf G.Fan (1984) zurückgeht.

Es sei G ein Graph ohne Artikulation mit mindestens drei Ecken. Erfüllen alle Eckenpaare x, y vom Abstand 2 die Bedingung \begin{eqnarray}\max\{d_{G}(x),d_{G}(y)\}\geq \vert E(G)\vert/2,\end{eqnarray}so ist G Hamiltonsch.