Math 344: Introduction to Combinatorics

Comments on Homework: Section 2.3

Problem 3

Question

What was that comment about Problem 3?

Answer

Use only parts (bcfik) of question 1, not all parts.

Question

Also, is the answer in text (at the back) for question 3 section 2.3 correct? (from b,c,f,i,k   b and i are the only two color critical?)

Answer

I believe so.

Question

I don't see how part i can be 3-colorable even if we remove one vertex?

Answer

Well, I think (i) originally requires 5 colours, so reducing the chromatic number would be to 4.

I stand corrected. The graph of (i) can be 4-coloured. Removing one vertex from (i) does not, I think, make the graph 3-colourable. Sorry about that.

Question

And, why doesn't part f work if you remove vertex i?

Answer

The point is that being colour critical means that if your remove any vertex the chromatic number decreases, not that if you remove a particular vertex it decreases.

Question

Just to clarify something if we remove vertex i for example in part f does that mean that all edges coming from vertex i are now gone or that now (h,c), (b,g), (a,e) would be connected?

Answer

The first: all edges coming from vertex i are now gone.

Problem 7

Question

I just wanted to check with you if these answers are correct for part (a):

1. k (k-1)³
2. k (k-1) (k-2) (k-3)
3. k (k-1)³ (k-2)

Answer

Yes. (Notice that the answer for part (a)(ii) is K₄, which we did in class.)

Problem 9

Question

What was that comment about Problem 9?

Answer

Answer this question for a graph of Canada, not the US. Here is a good map of the provinces of Canada from the Atlas of Canada.