Graph Theory Practice 1

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. (G and G' are duals.)

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? (Chinese Postman Problem: Given a connected graph, find a closed walk that visits each edge at at least once and which repeats (revisits) as few edges as possible.)

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?