0
$\begingroup$

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?

Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

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

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