# Hitting all cycles with three disjoint vertex sets

Is the following conjecture true or false? (Hopefully it is true — I need it as a lemma.)

For every undirected graph $G=(V,E)$ there exist three pairwise disjoint sets of vertices $V_1,V_2,V_3$ (whose union is not necessarily $V$) such that for every $i\in\{1,2,3\}$ and for every cycle $C\in G$, $C\cap V_i\neq \emptyset$.

That is, each $V_i$ hits all cycles in $G$, and the $V_i$ are pairwise disjoint.

-
The desired result in the second paragraph is untrue if $G$ is not connected (take $G$ to be the union of a cycle with some disconnected vertices). –  Vidit Nanda Jul 29 '13 at 14:40
If $G$ is a clique on at least 7 vertices then one of the classes must have 3 vertices and so contain a triangle disjoint from the remaining two classes. Have I understood the question correctly? –  Ben Barber Jul 29 '13 at 14:41
The vertex sets $V_1,V_2,V_3$ do not necessarily form a partition of $V$ (I clarified this in the question). So when $G$ is a cycle with some disconnected vertices, I just need each $V_i$ to be a vertex of the cycle. If $G$ is a clique, I would just take three different vertices. –  Ariel Jul 29 '13 at 14:46
Thank you for the correction. I still think cliques are a problem: if any one $V_i$ misses any 3 vertices of a clique then won't it be missing the corresponding triangle? –  Ben Barber Jul 29 '13 at 14:51
Oops, you're right... Thanks! –  Ariel Jul 29 '13 at 14:58

This is false for large complete graphs: eventually one of the $V_i$ will miss three vertices, and will not meet the corresponding triangle.
Even any graph containing $K_4$ fails. –  Andrew D. King Jul 29 '13 at 15:20