**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: