Homework Set 3: Coloring Problems

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

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 v_i (= number of vertices of valence i) of each of the graphs. If the graph is plane, also give the face vector p_i (= 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.

G:

H:

J:

M: