Problem

Source: ELMO Shortlist 2011, C2

Tags: induction, combinatorics proposed, combinatorics, Directed graphs, graph theory, Coloring



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.