/Solutions are available.

# 1. D4G3C

The GRAPH 3-COLORABILITY problem asks if it is possible to color all the vertices of a graph with no more than three colors, so that every edge has different-colored endpoints. It is well known that GRAPH 3-COLORABILITY is NP-complete.

Suppose that we restrict the problem to graphs where every vertex has at most four neighbors. Show that this restricted problem DEGREE 4 GRAPH 3-COLORABILITY of finding whether a graph with maximum degree 4 can be colored with three or fewer colors is also NP-complete, or give a polynomial-time algorithm that solves it. (Extra credit if you do both.)

# 2. D4G2C

Suppose now that we change the number of colors for D4G3C from three to two. Show that the resulting problem DEGREE 4 GRAPH 2-COLORABILITY of finding whether a graph with maximum degree 4 can be colored with two or fewer colors is also NP-complete, or give a polynomial-time algorithm that solves it. (Extra credit if you do both.)