Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
1. If two regular tetrahedra are pasted together along the edges of a face, a new convex 3-dimensional polyhedron P whose faces are all equilateral triangles is obtained. Here is a plane graph G which represents the graph of the polyhedron P involved.
a. Write down the v-vector (valence vector) and p-vector (face vector) associated with this graph.
b. Draw as many inequivalent nets for this polyhedron as you are able to find.
(i) For each of the nets N you find, write down a labeled spanning tree T(N) that you find in Figure 1 such that when you cut the edges of this spanning tree it gives rise to the net N.
(ii) For the tree T(N) find the associated dual tree T* associated with the dual
graph to the one shown in Figure 1.
d. How does the number of nets of P compare with the number of nets of the triangular prism (which is the dual of the graph in Figure 1) which consists of two equilateral triangles and three squares.
2. Find a plane connected graph H which has no loops and multiple edges and for which every vertex has degree at least 3, but where one can find a different embedding of H, H*, which has a different face vector from H. (Note that H* must be isomorphic to H as a graph.)
Write down the associated vertex vector and face vector for H and H*.
3. Prove or disprove that one can have a 3-valent graph which has exactly one edge which is a bridge.
4. A small city is laid out as a series of concentric circles and spokes emanating from a hub in the center. Suppose there are C concentric circles and s spokes. Assume all the edges of a graph representing such a city as having weight one. Find a formula for solving the Chinese postman problem for the graph associated with such a city in terms of C and s. Figure 2 below shows the situation for C = 2 and s = 6.