Graph Theory Practice 2

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. For the plane graph below: Figure 1

a. Write down the valence of each vertex of the graph.

b. Write down the number edges of each face of this graph. (Don't forget the infinite face.)

c. Does this graph have an Eulerian circuit?

d. Does this graph have a Hamiltonian circuit?

2, If G is a plane graph let vi denote the number of vertices of G of valence i. Furthermore, let pi denote the number of faces of G with i sides. For the graph in Figure 1 write down the non-zero values of vi and pi. (When written in "vector" form these numbers are sometimes called the valence vector and face vector of the graph, respectively.

Repeat this exercise for the graph in Figure 2. Figure 2

3. The graph in Figure 3 is a planar graph but the drawing shown is not a plane drawing. Figure 3

a. Write down the valence vector for the graph in Figure 3.

b. Draw a plane drawing D of the graph in Figure 3, and write down the face vector for your plane drawing.

c. Is it possible to draw an additional plane drawing D* of the graph in Figure 3 but one which has a different face vector from the face vector of D?

Note: If this can happen it means that isomorphic graphs can be drawn in the plane so that the face structures of the isomorphic graphs is different!

d. Does this graph have an Eulerian circuit?

4. Definition: A tree is a connected graph which has no circuits.

a. Can you draw a tree with the valences, 5, 1, 1, 1, 1, 1

b. Can you draw a tree with the valences 4, 1, 1, 1, 1

c. Can you draw a tree with the valences 4, 2, 2, 1, 1, 1, 1

d. Can you draw a tree with the valences 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1

e. If you were able to draw a tree for a. - d. are you able to draw a second tree which is not isomorphic to the first one you drew?

f. Write down the face vectors for each tree that you draw.

g. What are some of the properties of trees that you notice based on observation of graphs which are trees.

5. Can you draw a plane graph with exactly two faces?

6. Can you draw a plane graph with exactly three faces?

7. a. Is the graph below connected?

b. Write down the valence vector for this graph.

c. Does this graph have an Eulerian circuit? 8. Eulerian circuit problems often come up in the context of urban operations research. The realistic extension of this circle of ideas is known as the Chinese Postman Problem. This is because "real world graphs" rarely have Eulerian circuits. A common application of the Chinese Postman Problem, which involves finding the minimum cost route that starts and ends at the same vertex of a graph, involves snow removal. Furthermore, it is assumed the graph involved has positive weights on its edges and one wants the minimum cost route to traverse each edge at least once.

Find as many applications oriented situations that have a flavor similar to snow removal and for which the Chinese Postman model might apply. How are these problems you describe alike and how are they different?

9. For each of the graphs below write down an Eulerian circuit for the graph if there is one. Otherwise, solve the Chinese postman problem for the graph assuming weights of 1 for each edge. This means finding an optimal route as well as the length of this route.

a. b. c. 