1
$\begingroup$

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?

  • 0
    @Timothy Wagner: well, for my part, it's no huge deal either way.2010-11-28

1 Answers 1

3

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?