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?
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 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?