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
    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.2010-11-27
  • 0
    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.2010-11-27
  • 0
    Imagine you use one color 8 times and the other four colors once.2010-11-27
  • 1
    @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.2010-11-27
  • 0
    @Pete: The OP already knows the answer. So I did not assume it was a homework problem. I am not the only one who has given a similar answer.2010-11-27
  • 0
    Its a question from an old exam that I'm using to review. The scenario of using one color to color say 8 pieces crossed my mind, but since this rule was not explicitly defined in the question, I figured they meant that they went in order to color each vertex.2010-11-27
  • 0
    @Timothy Wagner: the word "homework" is ambiguous. On this site I tend to use it to mean something that the student should work out for him/herself in the context of a course they are taking. (It need not be turned in or graded.) In this case, I guessed that the student had turned in some assignment and this problem had been marked incorrect. It turns out it was an exam, which is similar....2010-11-27
  • 0
    @Pete L. Clark: Yesterday I provided a hint to a question which looked like HW and someone downvoted me for not giving a complete answer. So it's difficult to please everyone.2010-11-27
  • 0
    ...I wonder why the instructor didn't explain the mistake. Possibilities include: (i) she was too busy to do so and was possibly planning on doing it later, perhaps in class, (ii) she thought it was better if the student thought about it himself first. If I were the instructor, either way I would not be thrilled that the student asked the question on the internet, and in case (ii) I would be especially disappointed if he received a complete answer. Again, these are just my opinions, and I am not scolding you, but rather trying to explain my point of view.2010-11-27
  • 0
    @Timothy Wagner: "So it's difficult to please everyone." That's certainly true, so you have to do what you think is right. If it helps, I found the question you got downvoted on yesterday and upvoted your answer: in our economy, +1 + -1 = gain of 8 rep.2010-11-27
  • 0
    @Pete L. Clark: That's exactly what I did on both occasions. I thought it was more important for the OP to realize how to apply the pigeonhole through an example (or a non example) than to necessarily "solve" a problem for which the answer was already known to the OP. Also, this is only one way of coloring and the OP can still think about many other ways of coloring under these conditions.2010-11-27
  • 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?