**Graph Theory Practice 4: Duals, Vertex Vectors and Face Vectors
**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

1. Draw all the trees with 6 vertices which have maximal valence 4.

2.

a. Write down the face and vertex vectors for G

b. Write down the face and vertex vectors for G'

3. Draw the duals of the plane graphs below:

a.

i. Write down the vertex and face vectors of the dual graph.

b.

i. Write down the vertex and face vectors of the dual graph.

ii. If the Chinese postman problem is solved for the graphs above how many edges would be repeated?

c.

d.

i. Does the graph above have an Eulerian circuit? If so write one down starting at vertex 9.

ii. Does the dual graph have an Eulerian circuit? What is the number of repeats required in the solution of the associated Chinese postman problem?