Joseph Malkevitch: Geometric Structures: Basic Graph Theory
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York 11451
1. For each of the 10 graphs below:
a. How many vertices does the graph have?
b. How many edges does the graph have?
c. What is the degree sequence of the graph?
d. If the graph is planar, redraw the graph as a plane graph, and determine the number of faces with i sides for each value of i that occurs.
2. Use the information you record above, as well as any other invariant information you can compute to determine which pairs (or larger groups of graphs) are mutually isomorphic and which ones are not.
3. For each of the degree sequences you found in 1.(c) can draw an graph different from (non-isomorphic) the one that produced that degree sequence?