## 4.13 question clarification |
paulinalin |
---|---|

Since the question says that there are 5 different colors to choose from, does that imply that we should consider the possibility that vertices that aren't connected by an edge could be the same color? Do we also consider the case in which all of the vertices are different colors? Thanks! |

weisbart: Jan. 20, 2015, 5:32 p.m. |
---|

Certainly, if vertices are not connected then they can be the same color. The question is, how many cases do we need to consider. We hope to consider as few as possible. Here is a way to start. Lets label the vertices TopRight, TopLeft, BottomLeft, BottomRight. Suppose I claim that TopRight has five possibilities so TopLeft has four. Since TopLeft is now given, BottomLeft has four. Now BottomRight must be different from both TopRight and BottomLeft, so there are three possibilities. Answer is $5\times 4\times 4\times 3$. \[\] This answer is incorrect. Why? Does the reason it is incorrect give you a hint as to how to select and use a disjoint partition? |

NatalieNguyen2F: Jan. 21, 2015, 9:49 a.m. |
---|

I considered two cases. Case 1: Two vertices are the same color. Case 2: No two vertices are the same color. In Case 1, Top Left has 5 possibilities, Top Right then has 4 possibilities, Bottom Right has 1 possibility since it must match Top Left, and Bottom Left has 4 possibilities since its only restriction is that it cannot match the color of Top Left or Bottom Right. This gives me 5 x 4 x 1 x 4. In Case 2, Top Left has 5 possibilities, Top Right has 4 possibilities, Bottom Right now has 3 possibilities because it must not match the color of either Top Left or Right, and Bottom Left has 2 possibilities giving me 5 x 4 x 3 x 2. The total possibilities would then be:(5x4x1x4) + (5x4x3x2) However, the answers in the book say that in Case 2, the last vertice has 3 possibilities instead of 2, why is that? |

weisbart: Jan. 22, 2015, 9:54 p.m. |
---|

You have it almost perfect. The point is that the bottom right corner could have 3 possibilities, not 2. It can have the same color as the top left. In Case 1 and Case 2, it's not that two vertices have the same color, it's that TopRight and BottomLeft are the same or not. |