Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

As the question asks, is it possible for a graph to have a chromatic number larger than three without it having a 4 vertice complete graph as a sub-graph?

share|cite|improve this question
In general, there's no "easy" characterization of 3-colorability. Determining whether a graph is 3-colorable is NP-complete, so no characterization can be in P (such as checking whether it contains $K_4$, which is $O(n^4)$). – Jeremy Hurwitz Oct 31 '12 at 7:08
up vote 10 down vote accepted

Here's a simple counterexample with 6 vertices. Take a 5-cycle $C_5$. Add a new vertex $A$ and connect it by an edge with each vertex of $C_5$. The resulting graph is not 3-colorable. It it were 3-colorable, then $C_5$ would be 2-colorable, which it isn't.

Wheel graph

share|cite|improve this answer
@Douglas S. Stones This is offtopic, but what software did you use to draw the diagram? – Dan Shved Nov 2 '12 at 12:15
I pinched it from Wikipedia: here; listed as "Released into the public domain (by the author)." It would be possible to draw it this way using tikz. – Douglas S. Stones Nov 2 '12 at 21:56
question about this. doesn't Dirac's theorem say that if a graph is $4$-colorable then it must contain a subdivision of $K_4$? If this example is correct, wouldn't that prove the theorem wrong? – LeBron James Feb 15 at 5:01
@LeBron This example is correct, but it doesn't prove the theorem wrong. The graph on the picture does contain a subdivision of $K_4$, you just need to look for it carefully. To see the subdivision, just erase any two edges incident with the central vertex. – Dan Shved Feb 15 at 7:38
yes, thank you. I think i mixed up the concept of subgraph vs subdivision. – LeBron James Feb 15 at 19:05

I think this is the example referred to by Jeremy Hurwitz (the "squash" corresponding to vertices 4,5,6,7)

enter image description here

share|cite|improve this answer

A non-constructive counter-example comes from a theorem of Erdős: For any $\chi$ and $g$, there exists graphs of chromatic number at least $\chi$ and girth at least $g$. If we pick $g=\chi = 4$ then there exists a graph which is not $3$-colourable and is triangle free and therefore cannot possible contain a $K_4$ sub-graph.

share|cite|improve this answer

Let $G$ be a square with one diagonal. Note that the opposite corners must have the same color in any 3-coloring. We can therefore use this gadget to replace any vertex of a graph without changing its 3-coloarability.

So, for example, we can take $K_4$ and replace one vertex with $G$ (connect two of the edges to one corner and the third edge to the other corner).

There's probably a smaller counter example.

share|cite|improve this answer
What's a squash? – EuYu Oct 31 '12 at 7:09
Sorry! That should have said "square with one diagonal". I've fixed it. – Jeremy Hurwitz Nov 1 '12 at 15:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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