# Pigeonhole principle question

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?

-
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

## 1 Answer

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?

-