A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?

Question

Maybe I am missing something, but found potential counterexample to a conjecture of Nash-Williams.

According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS

The outdegree and indegree sequences of digraph $G$ are $d_1^+ \le \cdots \le d_n^+$ and $d_1^- \le \cdots \le d_n^-$. Note that the terms $d_i^+$ and $d_i^-$ do not necessarily corresponds to the degree of the same vertex of $G$.

Conjecture 1 (Nash-Williams). Suppose that $G$ is a strongly connected digraph on $n \ge 3$ vertices such that for all $i < n/2$

(i) $d_i^+ \ge i + 1$ or $d_{n-i}^- \ge n - i$,

(ii) $d_i^- \ge i + 1$ or $d_{n-i}^+ \ge n - i$,

Then $G$ contains a Hamilton cycle.

The potential counterexample is $G$ on $6$ vertices with edges:

[(0, 3), (0, 5), (1, 4), (1, 5), (2, 3), (2, 4), (3, 0), (3, 2), (3, 4), (3, 5), (4, 0), (4, 1), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]

$G$ is strongly connected and by inspection the degree sequences satisfy the hypotheses for $i \in [1,2]$ (both degree sequences are $[2, 2, 2, 4, 4, 4]$).

Nonhamitlonicity was shown using exhaustive search, sage 5.6 and Max Alekseyev's hamiltonian cycle counting pari program.

Is this really a counterexample to the conjecture of Nash-Williams?

Drawing of $G$:

Answer 1

I realize this question was asked seven years ago and hasn't had a comment in four years, but I just came across it and thought it might be worth sharing what I've learned.

As @HughThomas mentions, since $\{0,1,2\}$ is an independent set, the question boils down to whether the bipartite digraph between $\{0,1,2\}$ and $\{3,4,5\}$ has a Hamiltonian cycle. I wondered whether your example could be generalized for all $n=4k+2$. To generalize your example, we take sets $X=\{x_1, x_2, \dots, x_{2k+1}\}$ and $Y=\{y_1, y_2, \dots, y_{2k+1}\}$. We make $X$ an independent set and add all possible edges inside $Y$. The idea is to come up with a bipartite digraph $D$ between $X$ and $Y$ such that every vertex has indegree and outdegree at least $k+1$, but $D$ has no Hamiltonian cycle (as this would give a digraph having no Hamiltonian cycle with a degree sequence $[k+1,k+1,\dots,k+1,3k+1,3k+1,\dots,3k+1]$ satisfying Nash-Williams condition).

As it turns out D. Amar and Y. Manoussakis (see Theorem 1.7 and Fig. 1 in On the Meyniel condition for Hamiltonicity in bipartite digraphs by J. Adamus, L. Adamus, A. Yeo) proved that if $D$ is a bipartite digraph with $2k+1$ vertices in each part and every vertex has indegree and outdegree at least $k+1$, then $D$ has a Hamiltonian cycle unless $D$ is exactly your digraph on 6 vertices! (that is, the important part between the sets $\{0,1,2\}$ and $\{3,4,5\}$)

Note that if $n=4k$ you can create a bipartite digraph between $X=\{x_1, x_2, \dots, x_{2k}\}$ and $Y=\{y_1, y_2, \dots, y_{2k}\}$ in which every vertex has indegree and outdegree at least $k$ and there is no Hamiltonian cycle, but the resulting degree sequence will be $[k,k,\dots,k,3k-1,3k-1,\dots,3k-1]$ which just barely fails the Nash-Williams condition.

So my guess is that the conjecture is safe for all $n\neq 6$.