More Final Review Problems

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

a. Draw G - e

b. Draw G - f

c. Draw G - edge bd

d. Draw G - a

e. Draw G - edge ie

f. List the bridge edges of G

g. List the cut vertices of G

h. Draw the graph induced by the set of vertices: { a, d, e, i }

i. Draw the graph induced by the set of vertices: {a, b, d, e, i }

j. Does the graph which is a 4-cycle arise as an induced subgraph of G?

k. Find a spanning tree of G

l. Draw the dual of the graph obtained by finding G - f as well as the "isolated" vertices h and g which result.

2. Given the graph H below:

a. Draw the dual of H ; b. If p_k denotes the number of faces with k sides in a plane graph, find the p_k values for H and its dual; c. Find the minimum number of colors to color i. the vertices ii. the faces of H.