Problem Set III (Geometric Structures - Spring 2011)
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
1. For the graph H below:
a. How many vertices, edges, and faces does H have?
b. Write down the values of vi (number of vertices of valence i) of the vertices in H.
c. Write down the numbers pk (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 vi and pk 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 vi and pk 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.)