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

Suppose a graph with 12 vertices is colored with exactly 5 colors. By the pigeonhole principle, each color appears on at least two vertices. True or false?

The correct answer is false, but I assumed it to be true. Why is this so?

share|cite|improve this question
the pigeonhole principle tells you that at least 2 of the vertices have the same color. To me, it seems you are assuming some kind of additional rules on the coloring. – WWright Nov 27 '10 at 19:42
Without further restrictions, you could for instance, just use one color to color 8 vertices and use each of the other 4 for exactly one vertex. – Timothy Wagner Nov 27 '10 at 19:44
Imagine you use one color 8 times and the other four colors once. – Américo Tavares Nov 27 '10 at 19:45
Oh ok I see, thanks! – maq Nov 27 '10 at 19:46
@Timothy Wagner: from the context, it seems very likely that this is a homework problem of some sort. In my opinion, it would be more helpful if you left a little more for the OP to do. – Pete L. Clark Nov 27 '10 at 19:46
up vote 3 down vote accepted

The Pigeonhole Principle implies that there is at least one color which appears on at least $2$ vertices, not that each color appears. Is it possible to color $12$ vertices with five colors in such a way that one of the colors is used only on a single vertex?

share|cite|improve this answer

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.