Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
This problem asks us to “Follow the argument in the beginning of the proof of Theorem 5.”
There is no Theorem 5.
Ah, so there isn't. Tucker means Theorem 4.
Could you give some hints about how to solve question 2? (I have a feeling it has to do with using the fact that such a graph would have to have 6 regions, but I can't figure out how to show that this implies that there must be a triangle in the graph.)
Hint: if it can be 2-coloured, then it's bipartite. Now look at the remark (and formula) on page 41.
Did you notice that in part (a) the inequality should be ≥ not ≤?
Yes, thanks for the correction.
Could you give me some hints on how to solve question 6?
Notice that the set of vertices of a particular colour is an independent set.
For part (b), I understand how to get χ(G)q ≥ n, but I don't understand the relationship between minimum degree of a vertex and q. Could you explain what I'm supposed to do for part (b)?
Well, q is the size of the largest independent set. If each vertex has degree d, then each vertex is connected to d of its neighbours. Thus the largest independent set can have size at most n-d, or q ≤ n-d. Does that help?
It seems like this problem solves to χ(G) = (k-1)(k-4) Q(k). This obviously doesn't work as the only way to have k-4 is if the graph is at least 5 colorable, which is impossible as any planar graph is 4 colorable. However, we only proved that any planar graph is 5 colorable in class, and I'm assuming we can only use this fact for homework and exams, so how do I do this problem with only the 5-color theorem?
I think you've got a typo: it should be χ(G) = (k-2)(k-4) Q(k), I think. You don't have to use the 4 (or 5) Colour Theorem here. What is χ(G) when k=1? k=2? k=3? k=4? k>4? At least two of these are zero, and the rest aren't. Is this possible?