<p>The variation that I suggested was actually slightly different variation of <a href="http://www.ams.org/mathscinet-getitem?mr=0318000" rel="nofollow noreferrer">Woodal</a> theorem. Perhaps I saw it in the <a href="http://www.springer.com/new+&amp;+forthcoming+titles+%28default%29/book/978-1-84800-997-4" rel="nofollow noreferrer">Bang-Jensen and Gutin</a>'s book. At the time that I wrote a comment I didn't check the book for correctness. So to be sure I wrote the graph should be strongly connected. BTW, that statement holds because can be interpreted as a special case of Woodal theorem. In addition does not need strongly connectivity requirement.</p>

<p>This is the theorem 6.4.6 from <a href="http://www.springer.com/new+&amp;+forthcoming+titles+%28default%29/book/978-1-84800-997-4" rel="nofollow noreferrer">Bang-Jensen and Gutin</a>'s book:</p>

<blockquote>
  <p>Let $D$ be a digraph of order $n\ge 2$. If $\delta^+(x)+\delta^-(y) \ge n$ for all pairs of vertices $x$ and $y$ such that there is no arc
  from $x$ to $y$, then $D$ is hamiltonian.</p>
</blockquote>

<p>That means the answer to the second part of your question is also Yes.</p>

<p>There was a doubt about that whether $n$ is a tight bound or not. Here I try to answer it. We cannot reduce the requirement of at least $n$ to $k&lt;n$, consider the following graph. $a,b,c$ are making bidirected triangle, and $e,d$ are making a bidirected $k_2$. If hamiltonian cycle starts at $e$, it cannot go to $d$ in the next move because the only way for $d$ is using $b$ but, $b$ is the only way to back to $e$. On the other hand the Hamiltonian cycle after $e$ cannot go to $c$, because then the only back way to $e,d$ is going directly to $d$ to use $b$ in next moves, but again we are in the previous position. Also from the picture it's clear that every vertex has in and out degree at least $2$. So sum of every two arbitrary in-out is at least $4=5-1 = n-1$. We can extend these sort of graphs to arbitrary $n$.</p>

<p><img src="https://i.sstatic.net/yxmrm.jpg" alt="enter image description here"></p>

<p>P.S1: Sure the aforementioned theorem holds for simple digraphs. i.e digraphs without loop or parallel edges.</p>

<p>P.S2: I don't have a good Tex tool right now. So image is not good.</p>

CC BY-SA 3.0
2014-04-24T15:39:29.000Z
When there are only two authors, it is better to refer to them as "First and Second", rather than "First et al.", so they receive the credit they deserve.  Et al. ("and others") should only be used when the full author list is long enough that reproducing it would be awkward.
David Richerby
CC BY-SA 3.0
2014-04-24T14:45:28.620Z
2014-04-26T20:51:59.350Z
2014-04-26T20:51:59.350Z
Saeed
<p>The answer to your second question is affirmative:</p>

<blockquote>
  <p>If $\delta^+(G)+\delta^-(G) \ge n$ then $G$ is strongly connected</p>
</blockquote>

<p>Proof: Let $G$ be a graph which is not strongly connected. We will prove that $\delta^+(G)+\delta^-(G) &lt; n$. Write the decomposition of $G$ into strongly connected components. Let $S$ be a strongly connected component which is a sink (i.e. no edges go outside of $S$) and $T$ be a source (i.e. no edges go into $T$). Since no edges go $S$ to outside of $S$, then $\delta^+(G) \le \delta^+(S) \le |S|-1$. Similarly we get $\delta^-(G) \le |T|-1$, and taking these two things together we get $$\delta^+(G)+\delta^-(G) \le |S|+|T|-2 \le n-2 \ .$$ QED.</p>

CC BY-SA 3.0
2014-04-24T17:17:15.467Z
From this it seems like $\ge n-1$ is sufficient.
Geoffrey Irving
CC BY-SA 3.0
2014-04-25T00:47:44.820Z
@GeoffreyIrving Yes, it seems so.
greg
CC BY-SA 3.0
2014-04-25T14:37:09.853Z
This makes me wonder if n-1 is enough for Hamiltonicity.
R B
CC BY-SA 3.0
2014-04-26T09:15:16.970Z
@RB, No it's not enough.
Saeed
CC BY-SA 3.0
2014-04-26T18:54:49.480Z
Thanks @Saeed. Can you give example of such graph?
R B
CC BY-SA 3.0
2014-04-26T20:48:35.537Z
@RB, I updated my answer, actually this example is just counterproof of that theorem. In the way we prove the theorem if we have less $\delta^-+\delta^+ < n$ then we can obtain such graphs by reversing the proof.
Saeed
CC BY-SA 3.0
2014-04-26T21:51:18.327Z
@RB, But I'm wonder what is the minimum number of edges for a non-hamiltonian digraph D if $\delta^-+\delta^+ = n-1$.
Saeed
CC BY-SA 3.0
2014-04-26T21:56:24.043Z
@Saeed - I think that because of the comments system here no one else reads this. Perhaps you could start a new question?
R B
CC BY-SA 3.0
2014-04-26T21:56:45.550Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/14159/discussion-between-saeed-and-r-b)
Saeed
CC BY-SA 3.0
2014-04-24T16:25:10.847Z
2014-04-24T16:25:10.847Z
greg
<p>This is an extension of @Mobius answer to show a stronger claim:</p>

<blockquote>
  <p>If $\delta^+ + \delta^- \geq n-1$, then $\forall u,v\in V, d(u,v)\leq 2$.</p>
</blockquote>

<p>Proof:</p>

<p>If $(u,v)\in E$ we're done.</p>

<p>Denote $A=\{x\in V: (u,x)\in E\}, B=\{y\in V: (y,v)\in E\}$.</p>

<p>Notice that since $(u,v)\not \in E$, $A \cup B \subseteq V\setminus \{u,v\}$, hence $|A\cup B|\leq n-2$.</p>

<p>But then $$n-1 \leq \delta^+ + \delta^- \leq |A|+|B| =  |A\cup B| + |A\cap B| \leq n-2 + |A\cap B|$$</p>

<p>And therefore $|A\cap B| \geq 1$, i.e. $\exists w\in V:(u,w),(w,v)\in E$ and $d(u,v)=2$.</p>

<p>$ \blacksquare$.</p>

CC BY-SA 3.0
2014-04-26T21:20:35.287Z
2014-04-26T21:25:55.960Z
2014-04-26T21:25:55.960Z
R B
<p>Denote by  <span class="math-container">$\delta^+(G)$</span> the minimal out degree in <span class="math-container">$G$</span>, and by <span class="math-container">$\delta^-(G)$</span> the minimal in-degree.</p>
<p>In a <a href="https://cstheory.stackexchange.com/questions/22237/does-diracs-theorem-on-hamiltonian-cycles-only-apply-to-undirected-graphs">related question</a>, I've mentioned the Ghouila-Houri extension of <a href="http://en.wikipedia.org/wiki/Dirac%27s_theorem" rel="noreferrer">Dirac's theorem on Hamiltonian cycles</a>, which suggests that if <span class="math-container">$\delta^+(G),\delta^-(G) \geq \frac{n}{2}$</span> then G is Hamiltonian.</p>
<p>In his comment, Saeed have commented on a different extension that seems stronger, except it requires the graph to be strongly connected.</p>
<p>The strong connectivity was <a href="http://www.emis.de/journals/HOA/IJMMS/Volume14_4/875792.pdf" rel="noreferrer">proven redundant</a> for the Ghouila-Houri theorem about 30 years after it was first published, and I was wondering if the same holds for the extension Saeed presented.</p>
<p>So the question is:</p>
<blockquote>
<ol>
<li><p>Who proved (can anyone find the reference) that <span class="math-container">$\delta^+(G)+\delta^-(G) \geq n$</span> implies <span class="math-container">$G$</span> is Hamiltonian, given that <span class="math-container">$G$</span> is strongly connected?</p>
</li>
<li><p>Is the strong connectivity redundant here as well, i.e. Does <span class="math-container">$\delta^+(G)+\delta^-(G) \geq n$</span> imply strong connectivity?</p>
</li>
</ol>
</blockquote>
<hr />
<p>(Note that while the graph obviously has to be strongly connected for it to be Hamiltonian, I'm asking whether this condition is implied by the degree conditions).</p>

<reference-request><graph-theory>
Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?
R B
# Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

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

Denote by $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.

In a [related question](https://cstheory.stackexchange.com/questions/22237/does-diracs-theorem-on-hamiltonian-cycles-only-apply-to-undirected-graphs), I've mentioned the Ghouila-Houri extension of [Dirac's theorem on Hamiltonian cycles](http://en.wikipedia.org/wiki/Dirac%27s_theorem), which suggests that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian.

In his comment, Saeed have commented on a different extension that seems stronger, except it requires the graph to be strongly connected.

The strong connectivity was [proven redundant](http://www.emis.de/journals/HOA/IJMMS/Volume14_4/875792.pdf) for the Ghouila-Houri theorem about 30 years after it was first published, and I was wondering if the same holds for the extension Saeed presented.

So the question is:

> 1. Who proved (can anyone find the reference) that $\delta^+(G)+\delta^-(G) \geq n$ implies $G$ is Hamiltonian, given that $G$ is strongly connected?
> 2. Is the strong connectivity redundant here as well, i.e. Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

---

(Note that while the graph obviously has to be strongly connected for it to be Hamiltonian, I'm asking whether this condition is implied by the degree conditions).

**Tags:** reference-request, graph-theory

---

## 3 answers

### Answer by username_1 on 2014-04-24. Score: 8 | Accepted answer

The variation that I suggested was actually slightly different variation of [Woodal](http://www.ams.org/mathscinet-getitem?mr=0318000) theorem. Perhaps I saw it in the [Bang-Jensen and Gutin](http://www.springer.com/new+&+forthcoming+titles+%28default%29/book/978-1-84800-997-4)'s book. At the time that I wrote a comment I didn't check the book for correctness. So to be sure I wrote the graph should be strongly connected. BTW, that statement holds because can be interpreted as a special case of Woodal theorem. In addition does not need strongly connectivity requirement.

This is the theorem 6.4.6 from [Bang-Jensen and Gutin](http://www.springer.com/new+&+forthcoming+titles+%28default%29/book/978-1-84800-997-4)'s book:

> Let $D$ be a digraph of order $n\ge 2$. If $\delta^+(x)+\delta^-(y) \ge n$ for all pairs of vertices $x$ and $y$ such that there is no arc
> from $x$ to $y$, then $D$ is hamiltonian.

That means the answer to the second part of your question is also Yes.

There was a doubt about that whether $n$ is a tight bound or not. Here I try to answer it. We cannot reduce the requirement of at least $n$ to $k

![enter image description here](https://i.sstatic.net/yxmrm.jpg)

P.S1: Sure the aforementioned theorem holds for simple digraphs. i.e digraphs without loop or parallel edges.

P.S2: I don't have a good Tex tool right now. So image is not good.

> **Comments:**
> **username_2**: When there are only two authors, it is better to refer to them as "First and Second", rather than "First et al.", so they receive the credit they deserve.  Et al. ("and others") should only be used when the full author list is long enough that reproducing it would be awkward.  

---

### Answer by username_3 on 2014-04-24. Score: 7

The answer to your second question is affirmative:

> If $\delta^+(G)+\delta^-(G) \ge n$ then $G$ is strongly connected

Proof: Let $G$ be a graph which is not strongly connected. We will prove that $\delta^+(G)+\delta^-(G) < n$. Write the decomposition of $G$ into strongly connected components. Let $S$ be a strongly connected component which is a sink (i.e. no edges go outside of $S$) and $T$ be a source (i.e. no edges go into $T$). Since no edges go $S$ to outside of $S$, then $\delta^+(G) \le \delta^+(S) \le |S|-1$. Similarly we get $\delta^-(G) \le |T|-1$, and taking these two things together we get $$\delta^+(G)+\delta^-(G) \le |S|+|T|-2 \le n-2 \ .$$ QED.

> **Comments:**
> **username_4**: From this it seems like $\ge n-1$ is sufficient.  
> **username_3**: @GeoffreyIrving Yes, it seems so.  
> **username_0**: This makes me wonder if n-1 is enough for Hamiltonicity.  
> **username_1**: @RB, No it's not enough.  
> **username_0**: Thanks @Saeed. Can you give example of such graph?  
> **username_1**: @RB, I updated my answer, actually this example is just counterproof of that theorem. In the way we prove the theorem if we have less $\delta^-+\delta^+ < n$ then we can obtain such graphs by reversing the proof.  
> **username_1**: @RB, But I'm wonder what is the minimum number of edges for a non-hamiltonian digraph D if $\delta^-+\delta^+ = n-1$.  
> **username_0**: @Saeed - I think that because of the comments system here no one else reads this. Perhaps you could start a new question?  
> **username_1**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/14159/discussion-between-saeed-and-r-b)  

---

### Answer by username_0 on 2014-04-26. Score: 4

This is an extension of @Mobius answer to show a stronger claim:

> If $\delta^+ + \delta^- \geq n-1$, then $\forall u,v\in V, d(u,v)\leq 2$.

Proof:

If $(u,v)\in E$ we're done.

Denote $A=\{x\in V: (u,x)\in E\}, B=\{y\in V: (y,v)\in E\}$.

Notice that since $(u,v)\not \in E$, $A \cup B \subseteq V\setminus \{u,v\}$, hence $|A\cup B|\leq n-2$.

But then $$n-1 \leq \delta^+ + \delta^- \leq |A|+|B| = |A\cup B| + |A\cap B| \leq n-2 + |A\cap B|$$

And therefore $|A\cap B| \geq 1$, i.e. $\exists w\in V:(u,w),(w,v)\in E$ and $d(u,v)=2$.

$ \blacksquare$.


---

