**Assignment III: Graphs and Polyhedra (Spring, 2015)**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York

email:

__malkevitch@york.cuny.edu__

web page:

__http://www.york.cuny.edu/~malk/ __

1. Consider the graph R below:

a. Is R connected?

b. Is R 2-connected?

c. Is R 3-connected?

d. How many "independent paths" are there from vertex E to vertex C?

e. If v_{i} denotes the number of vertices of valence i in a graph write down the values of v_{i} for the graph R

f If p_{i} denotes the number faces with i sides in a plane graph, write down the values of p_{i} for the graph R.

g. a. Draw the dual graph R* of R.

h. Write down v_{i} and p_{i} for R*

i. Determine if R and R* have hamiltonian circuits (HC). If they do, show the HC by giving a plane drawing with "wiggled" edges indicating the HC.

A graph (no loops or multiple edges) is 3-polytopal if it is planar and 3-connected.

2. Draw if possible a plane graph drawing of a 3-polytopal graph whose valences are shown. If you are successful write down the values of p_{i} for the graph you find.

a. 4, 4, 4, 4, 4, 4; b. 4, 4, 4, 4, 4, 4, 4

c. 4, 4, 4, 4, 4, 4, 4, 4; d. 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

d. If you are unable to draw a 3-polytopal graph with the valences above were you able to draw ANY graph (no loops or multiple edges) with these valences?

3. a. Determine the vertex chromatic number for R and R*. Show a coloring that achieves the chromatic number. Do the color classes have the same size?

b. Determine the face chromatic number for R and R*. Show a coloring that achieves the chromatic number. Do the color classes have the same size?

c. Determine the edge chromatic number for R and R*. Show a coloring that achieves the chromatic number. Do the color classes have the same size?

Note: When one colors (subject to the usual coloring rules), say, the vertices of a graph, the number of vertices that get colored with color i, is the size of color class i.