Graphistan has $2011$ cities and Graph Air (GA) is running one-way flights between all pairs of these cities. Determine the maximum possible value of the integer $k$ such that no matter how these flights are arranged it is possible to travel between any two cities in Graphistan riding only GA flights as long as the absolute values of the difference between the number of flights originating and terminating at any city is not more than $k.$
Problem
Source: Turkish TST 2011 Problem 8
Tags: ceiling function, induction, graph theory, combinatorics proposed, combinatorics
24.07.2011 11:32
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$.
29.06.2013 21:54
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$
29.06.2013 22:07
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$ ...
29.06.2013 22:09
Ohhh thanks, I understand. Yes, I'm sorry.
29.06.2013 22:37
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
29.06.2013 22:40
Well, it agrees with my result, so it has a chance to be correct
29.06.2013 22:50
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
10.12.2024 20:09
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$