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?
|show 9 more comments|
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?