Homework Set 3: Coloring Problems
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
1. For each graph shown below, using the labels a, b, c, .... color the
a. vertices of the graph
b. color the faces of the graph (assuming the graph is plane)
c. color the edges of the graph
2. Give the valence vector vi (= number of vertices of valence i) of each of the graphs. If the graph is plane, also give the face vector pi (= number of faces with i sides).
3. List the vertices of the graph if any which are:
a. Cut vertices
b. Cut edges (bridges)
4. If the drawing shown is not a plane drawing, redraw the graph, as a plane drawing if possible.