A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to. David Yang.
HIDE: Stronger Version See here.Problem
Source: ELMO Shortlist 2011, C2
Tags: induction, combinatorics proposed, combinatorics, Directed graphs, graph theory, Coloring
18.04.2013 04:33
We prove by induction on $n$, the number of vertices in the graph. When $n = 3$ the result clearly holds (place each vertex in its own set), so we suppose the statement holds for some $n = N \ge 3$. Consider a digraph $G$ on $N + 1$ vertices where each vertex has out-degree $2$. By PHP, unless every vertex of $G$ has in-degree exactly equal to $2$, some vertex $v_0$ of $G$ has in-degree at most $1$. Consider the graph $G'$ we obtain by removing $v_0$ and the associated edges from $G$; $G'$ is a digraph on $N$ vertices where each vertex has out-degree at most $2$. By the induction hypothesis ("at most" is weaker than "exactly", so we can apply the inductive hypothesis directly), the vertices of $G'$ can be partitioned into $3$ sets such that no vertex $v$ is in the same set as both vertices it points to. We claim we can make a valid placement of $v_0$ into one of these sets. Indeed, if it's impossible to place $v_0$ in a set, either both vertices that $v_0$ points to are in that set, or one of the vertices pointing to $v_0$ (and all the other vertices that vertex points to) are in the set. The first case rules out at most one of the three sets, and since the in-degree of $v_0$ is at most $1$, the second case rules out at most one set. Hence it's possible to place $v_0$ in one of these sets such that the problem condition holds. Otherwise, every vertex has in and out-degree exactly $2$. Choose an arbitrary vertex $v_0$. Suppose it points to $v_a$ and $v_b$, and is pointed to by $v_1$ and $v_2$. Let $v'$ be the other vertex pointing to $v_a$. Finally, let $v_1'$ and $v_2'$ be the other vertices that $v_1, v_2$ point to, respectively. Consider the graph $G'$ we obtain by removing $v_0$ and the associated edges from $G$ and subsequently drawing the edges from $v_1$ and $v_2$ to $v'$ (now utilizing the full strength of the induction hypothesis). Every vertex of $G'$ has out-degree $2$, so by hypothesis the vertices of $G'$ can be partitioned into $3$ sets $S_1, S_2, S_3$ such that no vertex $v$ is in the same set as both vertices it points to. We can make a valid placement of $v_0$ in one of these sets unless (WLOG), $v_1, v_1' \in S_1$, $v_2, v_2' \in S_2$, and $v_a, v_b \in S_3$. Now remark $v' \not \in S_1, S_2$ since otherwise either $v_1$ or $v_2$ would be in the same set as the two vertices it points to. Then $v' \in S_3$. Now at least one of $S_1, S_2$ does not contain both vertices that $v_a$ points to; we can move $v_a$ from $S_3$ to this set (WLOG $S_1$) and maintain the validity of the partition since neither of the two vertices that point to $v_a$ (namely, $v$ and $v'$) are in this set. Finally, place $v$ in $S_3$; then $v_1$, $v_2$, $v_a$ are all in a different set from $v$ and we're done.
18.04.2013 05:02
hyperbolictangent wrote: Otherwise, every vertex has in and out-degree exactly $2$. Choose an arbitrary vertex $v_0$. Suppose it points to $v_a$ and $v_b$, and is pointed to by $v_1$ and $v_2$. Let $v'$ be the other vertex pointing to $v_a$. Finally, let $v_1'$ and $v_2'$ be the other vertices that $v_1, v_2$ point to, respectively. Here's a more conceptual approach (IMO): Take a partition that maximizes the number of (good) edges between distinct sets. If some $v$ belongs to the same set as its out-neighbors, moving $v$ to one of the other two sets (whichever has fewer in-neighbors of $v$) will add 2 good edges but kill at most 1 old one, which is impossible.
18.04.2013 05:52
Sorry, the argument is not clear to me. Suppose we have edges $av$, $bv$, $cv$, $dv$, $ev$, $fv$, $vx$, $vy$ (among possibly others) and the initial partition is $\{a, b, c, \ldots\}$, $\{d, e, f, \ldots\}$, $\{v, x, y, \ldots\}$. Moving $v$ to either of the other groups creates 2 and kills 3 good edges. Why can't this be the maximal partition? Edit: response via PM: math154 wrote: $v$ has in-degree greater than 2 here; I was just mentioning an alternative approach to the case in which all in-degrees and out-degrees are 2. Aha, I see, I missed that you were working in that special case. Objection withdrawn.
20.07.2013 04:16
Huh, is it just me or is all this rather overcomplicated? We could just delete one of the edges coming from every vertex; we end up with a graph with a bunch of connected components, each with exactly one (directed) cycle, and this is easy to 3-color. Just start by coloring the cycle (e.g. either 1212...12 or 1212...123 by parity) and iteratively pick a color for each remaining vertex that's different from the vertex it points to.
08.04.2019 16:25
It IS overcomplicated. Delete one outedge from every vertex, we claim that the resulting subgraph can be $3-coloured$: either it is the union of several vertex-disjoint cycles, or it has at least one vertex with indegree $0$. The former is obvious and the latter is trivial by induction. QED