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.

  • $\begingroup$ 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). $\endgroup$ Jul 29, 2013 at 14:40
  • $\begingroup$ 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? $\endgroup$
    – Ben Barber
    Jul 29, 2013 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – Ariel
    Jul 29, 2013 at 14:46
  • $\begingroup$ 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? $\endgroup$
    – Ben Barber
    Jul 29, 2013 at 14:51

1 Answer 1


This is false for large complete graphs: eventually one of the $V_i$ will miss three vertices, and will not meet the corresponding triangle.

  • 2
    $\begingroup$ Even any graph containing $K_4$ fails. $\endgroup$ Jul 29, 2013 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.