In der Theorie der gerichteten Graphen, einem der Teilgebiete der Graphentheorie, ist der Satz von Ghouila-Houri das Pendant zum Satz von Dirac in der Theorie der ungerichteten Graphen. Der Satz geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1960 zurück. Von mehreren Autoren wird hervorgehoben, dass der Beweis des Ghouila-Houri'schen Satzes um einiges schwieriger sei als der des diracschen.^[1][2][3]

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher gerichteter Graph ${\displaystyle D}$.

${\displaystyle D}$ sei stark zusammenhängend und habe zudem die Eigenschaft, dass an jedem Knoten ${\displaystyle v}$ für den Grad ${\displaystyle d_{G}(v)=d_{G}^{-}(v)+d_{G}^{+}(v)}$ in Bezug auf die Knotenzahl ${\displaystyle n(D)}$ durchweg die Ungleichung

${\displaystyle {d_{G}}(v)\geq n(D)}$

erfüllt ist.

Dann besitzt ${\displaystyle D}$ einen hamiltonschen Zyklus, also einen Zyklus, auf dem alle Knoten von ${\displaystyle D}$ genau einmal vorkommen.

Insbesondere gilt diese Aussage für den Fall, dass an jedem Knoten ${\displaystyle v}$ hinsichtlich Eingangsgrad und Ausgangsgrad die beiden Ungleichungen

${\displaystyle d_{G}^{-}(v)\geq {\frac {n(D)}{2}}}$

und

${\displaystyle d_{G}^{+}(v)\geq {\frac {n(D)}{2}}}$

erfüllt sind.

Der Satz von Ghouila-Houri wurde von mehreren Autoren verschärft; so im Jahre 1973 von M. Meyniel wie folgt:^[4]

Ist ${\displaystyle D}$ ein endlicher stark zusammenhängender gerichteter Graph, der für je zwei verschiedene nicht benachbarte Knoten ${\displaystyle v_{1}}$ und ${\displaystyle v_{2}}$ die Ungleichung

${\displaystyle {d_{G}}(v_{1})+{d_{G}}(v_{2})\geq 2n(D)-1}$.

erfüllt, so besitzt ${\displaystyle D}$ einen hamiltonschen Zyklus.

• Alain Ghouila-Houri: Une condition suffisante d'existence d'un circuit hamiltonien. In: Comptes rendus de l’Académie des sciences Paris. Band 251, 1960, S. 495–497 (MR0114771). 
• Rudolf Halin: Graphentheorie. 2., überarbeitete und erweiterte Auflage. Wissenschaftliche Buchgesellschaft, Darmstadt 1989, ISBN 3-534-10140-5 (MR1068314). 
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• M. Meyniel: Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente. In: Journal of Combinatorial Theory. Series B. Band 14, 1973, S. 137–147 (MR0317997). 
• Robin J. Wilson: Einführung in die Graphentheorie. Aus dem Englischen übersetzt von Gerd Wegner (= Moderne Mathematik in elementarer Darstellung. Band 15). Vandenhoeck & Ruprecht, Göttingen 1976 (MR0434854 – Englische Vorlage: Introduction to Graph Theory, Longman, London 1975). 

1. ↑ Rudolf Halin: Graphentheorie. 1989, S. 110
2. ↑ Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 111–112
3. ↑ Frank Harary: Grapentheorie. 1974, S. 220
4. ↑ Halin, op. cit., S. 110, 304