There is a fairly known result for a complete digraph (tournament) $G$ on $n$ vertices that either it contains a Hamiltonian cycle, or else its vertices can be partitioned into two classes $A,B$, such that all $A-B$ edges are directed from $A$ to $B$ (as such, it even appeared in some ugly algebraic form as Poland's proposal on 1989 ILL). Thus we have to determine the least $k$ such that if $\max_{v\in G} |\deg^{+} v - \deg^{-} v| \leq k$ we may produce such a partition; for the next lowest value of $k$ any directioning of edges will contain a Hamiltonian cycle, and thus answer the problem. Let then assume such a partition $A,B$ with say, wlog $a = |A| \leq |B| = b$. Then $\sum_{v\in A} \deg_A^+ v = \sum_{v\in A} \deg_A^- v$, $\deg_G^+ v = \deg_A^+ v + b$, $\deg_G^- v = \deg_A^- v$ for all $v\in A$, so there will exist some $v\in A$ with $|\deg_G^{+} v - \deg_G^{-} v| \geq b \geq \lceil n/2 \rceil$. For us, let us then build $|A| = 1005$, $|B| = 1006$. Take $\mathbb{Z}_{1005}$ as $A$, with edges $\overrightarrow{ij}$ for $j = i+1,\ldots, i+502$, so $\deg^{+} i = \deg^{-} i = 502$ for all $i$. Take another copy of $A$, and another $1006$-th vertex $u$, in order to make $B$, with $503$ edges from $B' \subset B$ towards $u$ and another $502$ edges from $u$ towards $B \setminus B'$. This is a good example, with $\max_{v\in G} |\deg^{+} v - \deg^{-} v| = 1006 = \lceil 2011/2 \rceil $. Therefore the required value for $k$ is $1005$.

Can somebody explan why I obtained the answer $k=2008$? Here is my solution: Assume $k=2008$. Then, every vertex has at least one edge going in, and one edge going out. Now, assume the statement is false and there exist two cities $A$ and $B$ such that you can't travel from $A$ to $B$. Therefore, the edge $AB$ must be $B \rightarrow A$. But $A$ has at one edge going out, say $A \rightarrow A_2$. If the edge $BA_2$ $A_2 \rightarrow B$, a path from $A$ to $B$ exists ($A \rightarrow A_2 \rightarrow B$), contradiction. So $B \rightarrow A_2$. But $A_2$ has at least one edge going out, say $A_2\rightarrow A_3$. Same argument, we have that $B \rightarrow A_3$. We apply this argument over and over again and eventually we have vertices $A_2, ..., A_{2009}$ such that $B \rightarrow A_i$ for $1 \le i \le 2009$, and also $B \rightarrow A$. So $B$ has no edges going out, contradiction! Therefore we were wrong and the graph is strongly connected, giving us the answer $k=2008$

What tells you that at each step you get a new $A_i$ ? Maybe the one edge out of $A_3$ is back to $A, A_1$ or $A_2$ ...

Ohhh thanks, I understand. Yes, I'm sorry.

Ok I have found a correct solution. Take the answer to the problem $k=R$, and suppose we take a graph with $k=R+1$, so the maximum difference of edges going into $V$ and the ones going out of V is $R+1$. Now, it's widely known that a tournament is strongly connected iff it has a Hamilton cycle. But this tournament isn't strongly connected and so it doesn't have a Hamilton cycle. Now, suppose we partition the vertices of the graph into the sets $A$ and $B$. If for any partition, there are edges going from $A$ to $B$ and from $B$ to $A$, it's easy to see we can create a Hamilton cycle. How? By induction on the number of vertices. The base case is trivial. Now, if any graph with $n-1$ vertices that satisfies that for any partition $A \cup B$ there are edges from $A \rightarrow B$ and viceversa, is strongly connected, take $G$ a graph with $n$ vertices that satisfies the same property. Erase/forget one vertex from $G$ and we are left with $G_1$ with $n-1$ vertices that satisfies the property, therefore it's strongly connected, so there's a Hamilton cycle $V_1...V_{n-1}$. Now take the erased/forgotten vertex $V$. Taking $A=\{V\}$ we see V has some edges going in and some going out. It is easy that two of those will be consecutive (in $V_1...V_{n-1}$), say $V_i \rightarrow V \Rightarrow V_{i+1}$ and so $V_1...V_iVV_{i+1}...V_{n-1}$ is a hamilton cycle, thus completing the induction. But our graph has no hamilton cycle therefore exist partition $A \cup B$ such that all edges are $B \rightarrow A$ (no $A \rightarrow B$.). Say $a$ vertices in $A$, $b$ in $B$. There's a vertex in $A$ with at most $\frac{a-1}{2}$ edges going out, obviously, so for that vertex, the difference of (#edges going in)-(#edges going out) is at least $b$. So $R+1 \ge b$ Similarly $R+1 \ge a$. Therefore $2(R+1) \ge a+b = 2011$ so that $R+1 \ge 1006$ and $R \ge 1005$. Now we must prove any graph that has $k=1005$ has a Hamilton cycle. Suppose not, so we can partition it in $A \cup B$ so that there are no edges $A \rightarrow B$. Say $A$ has $a$ elements, $B$ has $b$. WLOG $a \ge 1006$. Take the vertex with the least number of edges going in in $B$. It has at most $\frac{b-1}{2}$ edges going out and therefore the difference $d = (\#edges going in)-(\#edges going out)$ satisfies $1005 \ge d \ge a \ge 1006$, contradiction. ANSWER: 1005

Well, it agrees with my result, so it has a chance to be correct

haha I hope it is, let me read your solution to see if they are similar. I basically just proved: Strongly connected iff hamiltonian cycle iff all partition $A \cup B$ of the vertices satisfy there are edges going from $A \rightarrow B$ and viceversa. After that, you look at the number of vertices in A and in B and finish rather quickly. EDIT: WOW! I didn't know what i had proved was a known result that would've saved me a lot of time in my solution But I think my solution is the same as yours

Answer is $k=1005$. Take the graph interpretation. First, we present two lemmas. Lemma: If a tournament has $2k+1$ vertices, then we can orient its edges such that each vertex has both outdegree and indegree $k$. If a tournament has $2k$ vertices, then we can orient its edges such that each vertex has outdegree and indegree $k$ or $k-1$. Proof. Let's induct on $k'$s. First, we will show that for odds. It holds for $1$ vertex, $3$ vertices. Let it be true for some $2k-1$. Then, add two vertices $u,v$ and let $u$ point $1,3,\dots,2k-1$ which point $v$, let $v$ point $2,4,\dots,2k-2$ which point $u$. The old vertices have degree $k$ for out and in. Let $v$ point to $u$ which provides the equalities. Now, we prove the latter case where there are even number of vertices. It holds for $2$, let it be true for $2k-2$ vertices. Add two vertices called $u,v$ to the graph. Let $u$ point to $1,3,\dots,2k-3$ which point to $v$ and let $v$ point to $2,4,\dots,2k-2$ which point to $u$. WLOG $u$ points to $v$ and the old vertices' difference of outdegree and indegree does not change and the difference for $u,v$ is $1$ or $0$ as we have expected. Lemma: In a tournament, there exist two vertices $A$ and $B$ such that there is no path starting at $A$ and ending at $B$ if and only if the graph can be partitioned into $X,Y$ such that the vertices in $X$ point to each vertex in $Y$. Proof. First direction is obvious, let's prove the latter one. Suppose that there is no path from $A$ to $B$. Let $S$ be the set of vertices $A$ can reach via some path and consider $G-\{S\cup A\}=T$. Note that each vertex in $T$ points to $A$. Also if some $u\in S$ points to a vertex $v\in T$, then there would exist a path from $A$ to $v$ which is impossible by our assumption. Hence we can choose $X=A\cup S$ and $Y=T$. Counterexample for $k\geq 1006$: Consider two parts $X,Y$ such that each vertex in $X$ points to each vertex in $Y$. Also let $|X|=1006$ and $|Y|=1005$. If a graph's vertices have both indegree and outdegree either $\lceil\frac{|G|}{2}\rceil$ or $\lfloor \frac{|G|}{2}\rfloor$, then let's call this graph balanced. We choose $X,Y$ balanced and we see that $k\leq 1005$. $k=1005$ works: By the latter lemma, if $\text{difference}=|\text{outdegree}-\text{indegree}|\leq 1005$ and we cannot reach from $A$ to $B$, then we can partition the graph into $X,Y$ such that each vertex in $X$ points to each vertex in $Y$. Let $u,v$ be the vertices with maximum and minimum difference in $X,Y$ respectively. \[\text{difference}(u)\geq |Y|+\frac{|X|-1}{2}-\frac{|X|-1}{2}=|Y|\]\[\text{difference}(v)\geq |X|+\frac{|Y|-1}{2}-\frac{|Y|-1}{2}=|X|\]One of $|X|,|Y|$ is at least $1006$ which gives a contradiction as desired.$\blacksquare$