Joseph Malkevitch: Assignment 3: Graphs and Polyhedra/TITLE> </HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html;CHARSET=macintosh"> <meta name="KEYWORDS" content="math, mathematics, maa, undergraduate, education, college admissions, SAT, college search, AP, York, College, CUNY, New York, Jamaica, City University, Malkevitch, CUNY Teacher Academy, York Teacher Academy, mathematical contexts, mathematical modeling, taxicab geometry, geometry, survey of geometry, geometric structures, graph theory, geometry, teaching geometry, coloring, plane graphs, polyhedra, Steinitz's Theorem, graphs, valences "> <TITLE>Joseph Malkevitch: Geometric Structures

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.