Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

Question

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

In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian cycles, 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 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).

Answer 1

The variation that I suggested was actually slightly different variation of Woodal theorem. Perhaps I saw it in the Bang-Jensen and Gutin'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'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<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.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.

Answer 2

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.

Answer 3

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$.