**Graph Theory Practice: SET G: (Plane graphs)**

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 graph G below:

a. Draw G - v for each vertex of G

b. Draw G - e for each edge of G

c. List the cut vertices of G if any.

d. List the bridges (cut edges) of G if any.

e. Draw the line graph of G. If the line graph of G is planar draw a plane embedding of the line graph.

2. Repeat the questions above for the graph G below:

Additionally:

f. Draw the medial graph of the graph above. How many vertices, edges and faces does this medial graph have?

g. Is the graph above 3-polytopal? If not, what is the minimum number edges that can be added to the graph to make it 3-polytopal?

h. Does the graph above have an Eulerian circuit? If so write one down. If not, give a reason, and find a Chinese Postman tour for this graph.