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 vi denotes the number of vertices of valence i in a graph write down the values of vi for the graph R

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

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

h. Write down vi and pi 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 pi 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.