<p>While Dirac's theorem wasn't intended/proved for directed graphs, it was extended to directed graphs by GHOUILA-HOURI in 1960 ("Une condition suffisante d’existence d'un circuit hamiltonien").</p>

<p>Their requirements, however, were that each vertex should have both out-degree <strong>and in-degree</strong> of at least $n/2$, which is not the case in your graph.</p>

<p>One of the original conditions of GHOUILA-HOURI, as Saeed mentioned, is that the graph is strongly connected. In fact, the degree conditions <a href="https://cstheory.stackexchange.com/questions/22247/does-deltag-delta-g-geq-n-imply-strong-connectivity/22299#22299">are strong enough</a> for only diameter $\leq 2$ graphs to be considered.</p>

CC BY-SA 3.0
2014-04-23T21:06:00.247Z
2014-04-28T21:23:57.780Z
2017-04-13T12:32:28.743Z
R B
<p>Does <a href="http://en.wikipedia.org/wiki/Dirac%27s_theorem">Dirac's theorem on Hamiltonian cycles</a> only apply for undirected graphs? If the theorem applied to directed graphs, the graph with the following adjacency list should have a Hamiltonian cycle, but I can't find one.</p>

<blockquote>
  <p>$0$: $1$ $2$ $3$</p>
  
  <p>$1$: $2$ $3$</p>
  
  <p>$2$: $1$ $3$</p>
  
  <p>$3$: $1$ $2$</p>
</blockquote>

CC BY-SA 3.0
2014-04-23T20:56:49.267Z
Yes Dirac Theorem is for undirected graphs, directed variation is this(is not by dirac): If $G$ is a strongly connected graph and $\delta^+(G)+\delta^-(G) \ge n$. $\delta^+(G)$ is minimum out degree and $\delta^-(G)$ is minimum in degree of $G$.
Saeed
<graph-theory>
Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs?
Paweł Kaftan
# Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs?

(Asked by: username_0 on 2014-04-23)

Does [Dirac's theorem on Hamiltonian cycles](http://en.wikipedia.org/wiki/Dirac%27s_theorem) only apply for undirected graphs? If the theorem applied to directed graphs, the graph with the following adjacency list should have a Hamiltonian cycle, but I can't find one.

> $0$: $1$ $2$ $3$
>
> $1$: $2$ $3$
>
> $2$: $1$ $3$
>
> $3$: $1$ $2$

**Tags:** graph-theory
> **Comments:**
> **username_1**: Yes Dirac Theorem is for undirected graphs, directed variation is this(is not by dirac): If $G$ is a strongly connected graph and $\delta^+(G)+\delta^-(G) \ge n$. $\delta^+(G)$ is minimum out degree and $\delta^-(G)$ is minimum in degree of $G$.  

---

## 1 answers

### Answer by username_2 on 2014-04-23. Score: 11 | Accepted answer

While Dirac's theorem wasn't intended/proved for directed graphs, it was extended to directed graphs by GHOUILA-HOURI in 1960 ("Une condition suffisante d’existence d'un circuit hamiltonien").

Their requirements, however, were that each vertex should have both out-degree **and in-degree** of at least $n/2$, which is not the case in your graph.

One of the original conditions of GHOUILA-HOURI, as Saeed mentioned, is that the graph is strongly connected. In fact, the degree conditions [are strong enough](https://cstheory.stackexchange.com/questions/22247/does-deltag-delta-g-geq-n-imply-strong-connectivity/22299#22299) for only diameter $\leq 2$ graphs to be considered.


---

