Homework 5 (due Thursday, September 23rd)

1.  3H in Van Lint.  (See the hint.)

2.  Show that if a the vertices of a simple graph G can be colored with 4 colors, adjacent vertices having different colors, then the edges of G can be colored with 3 colors so that the 3 edges of every triangle have different colors.

3.  Show that the unit distance graph in the plane has chromatic number at most 7.  (Hint: Use the tiling of the plane by regular hexagons to show that the unit distance graph can be 7-colored.)

4.  3K in Van Lint.  (See the hint.)