Problem 1776

We want to find the largest integer $k$ such that a directed path exists from any vertex $v_1$ to any vertex $v_2$ in any directed complete graph $G$ with 2011 vertices satisfying $|\text{indeg}(v) - \text{outdeg}(v)| \le k$ for all vertices $v$. The answer is 1005.

Observe that $|\text{indeg}(v) - \text{outdeg}(v)|$ is always even. We first give a counterexample with $k=1006$. Let $V = X \cup Y$, $X = \{x_1, x_2, \dots, x_{1005}\}$, $Y = \{y_1, y_2, \dots, y_{1006}\}$, and $E = \{(x_i, x_j) : 1 \le i < j \le \max(i+502, 1005) \text{ or } 1 \le j \le \max(i-503, 0)\} \cup \{(y_i, y_j) : 1 \le i < j \le \max(i+503, 1006) \text{ or } 1 \le j < \max(i-503, 0)\} \cup \{(x_i, y_j) : 1 \le i \le 1005 \text{ and } 1 \le j \le 1006\}$.

Then $|\text{indeg}(v) - \text{outdeg}(v)| \le 1006$ for all $v \in V$ in the graph $G = (V, E)$, but there is no directed path from $y_1$ to $x_1$.

Now we will show that there is a directed path from any vertex to any vertex if $|\text{indeg}(v) - \text{outdeg}(v)| \le 1004$ for all vertices $v$. Note that if one of $\text{indeg}(v)$ and $\text{outdeg}(v)$ is less than 503, then the other is greater than 1507 and $|\text{indeg}(v) - \text{outdeg}(v)|$ is at least 1006. Therefore $\text{indeg}(v)$ and $\text{outdeg}(v)$ are both at least 503.

Let $v_1$ and $v_2$ be two distinct vertices in $G$. Let $V_1$ be the set of vertices that can be reached from $v_1$ and let $V_2$ be the set of vertices from which $v_2$ can be reached. Then all arrows with tail in $V_1$ have also their heads in $V_1$. Therefore the sum of $\text{outdeg}(v)$ for $v$ in $V_1$ is $\binom{|V_1|}{2}$. On the other hand, this sum must be at least $503|V_1|$. It follows that $|V_1| \ge 1007$. A similar argument shows that $|V_2| \ge 1007$. Hence $V_1$ and $V_2$ cannot be disjoint.