2
$\begingroup$

Is the statement below correct?

A graph which doesn't have a complete graph of order $4$ or more can be colored with $3$ colors, so that no two adjacent vertices have same color.

I don't know it is correct or not; if it is not correct, please someone give me a counterexample to that.

$\endgroup$
  • $\begingroup$ No two adjacent vertices have same color. $\endgroup$ – bigname May 5 '15 at 7:31
1
$\begingroup$

Counterexample: Take the cycle $C_5$ and add a sixth vertex which is adjacent to all of the old vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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