Two-way bounding problem 1

Quick check

Does your answer contain all three important elements?

  1. What is the chromatic number?
  2. Upper bound: why is this enough colors?
  3. Lower bound: why won't fewer colors work?

It's important to explicitly answer the question (item 1 above). The reader could probably figure it out from your answers to the other two items, but your job is to be clear and helpful.

If you are missing any of these elements, fill it in before proceeding further.

Perhaps you have constructed an argument that addresses points 2 and 3 together? Make sure it is clear to the reader that you have addressed both. It is very easy to lose points because the grader sees only one argument and interprets it as addressing only one of the two bounds.

Have you put the labels "upper bound" and "lower bound" on the right parts of your argument? For this problem, the upper bound will typically be a picture showing the coloring. The lower bound will typically involve finding a special subgraph or showing that it's not possible to color the graph with fewer colors.

Now look at the full solution.