Problem Set III (Geometric Structures - Spring 2011)

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 the graph H below:

a. How many vertices, edges, and faces does H have?

b. Write down the values of v_i (number of vertices of valence i) of the vertices in H.

c. Write down the numbers p_k (number of faces with k sides) for H embedded as shown.

d. Draw H - vertex 10. Is the resulting graph 3-polytopal?

e. Draw H - vertex 4. Is the resulting graph 3-polytopal?

f. Draw H - edge (7-10). Is the resulting graph 3-polytopal?

g. Draw the dual of H and write down the values of v_i and p_k for the dual.

h. Draw the medial graph of H. How many vertices, edges, and faces does the medial graph of H have? Write down the values of v_i and p_k for the medial graph.

i. How many vertices and edges does the line graph of H have? Is the line graph of H isomorphic to the medial graph of H?

j. Is graph H 3-polytopal?

k. How many paths are there in H between vertex 2 and vertex 4 which have only these vertices in common?

l. How many paths are there in H between vertex 10 and vertex 7 which have only there vertices in common?

m. Draw the line graph of the graph M below:

If the line graph of M is planar, draw a plane embedding of it.

n. Draw a spanning tree T of H with maximal valence 3 in the tree, and show how this tree T induces a spanning tree T* in the dual of H. (Comment: It is an unsolved problem if T and T* can always be chosen so both have maximal valence 3.)