# Coloring a graph with three colors

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.

• No two adjacent vertices have same color. – bigname May 5 '15 at 7:31

## 1 Answer

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