Assuming $G=(V,E)$ is a 3-colorable graph, then there are 3 disjoint independent subsets of $V$: $S_1,S_2,S_3$ such that $S_1 \cup S_2 \cup S_3=V$, by taking each $S_i$ to include the vertices of color $i$.

I wanted to know - if $G$ is not 3-colorable, then can it has 3 disjoint subsets that their union is $V$?

I think it can't be by the definition of 3-colorable.

Am I correct?



1 Answer 1


This sounds like homework, so you should try to prove it. The title, by the way, doesn't make sense.

Proof sketch. Suppose that you can partition the vertex set into three independent sets, $S_1, S_2, S_3$. Color the vertices in partition $S_1$ red, $S_2$ green, and $S_3$ blue.

Claim. This is a proper coloring, hence the graph is 3-colorable.

We conclude that if the graph is 3-colorable, then its vertex set can be partitioned into three independent sets.

  • $\begingroup$ Thank you very much! It is actually something that I thought of by myself, I just needed a verification. :) $\endgroup$
    – Geo
    Commented Feb 14, 2023 at 19:21

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.