This test covers HW I–VII: everything we've done so far in the book (that's up to Section 3.2, inclusive) and in class.
The points per problem are:
(1) 1 (2) 10 (3) 10 (4) 12 (5) 8 (6) 10 (7) 5 (8) 5 (9) 7 (10) 8 (11) 10 (12) 5 + 9 + (bonus) max 10The guidelines for the grades are:
A B C D F 80-100 65-79 47-64 40-46 0-39
A B C D F 84-100 62-83 42-61 36-41 0-35
Note: Due to an arithmetic error, there were 140 points on this test instead of the intended 150. The grading guidelines take account of that.
The guidelines for the grades are:
A B C D F 110-140 85-109 58-84 50-57 0-49
The size of a graph is the number of edges, |E(G)|.
G and H are isomorphic if there exists an isomorphism. They are not isomorphic if no isomorphism exists.
One kind of isomorphism is especially interesting. An automorphism of a graph G is an isomorphism of G with itself. Every graph has at least one automorphism, the identity automorphism, which is the identity function from V to V. Some graphs have no other automorphisms. Other graphs have many automorphisms. See the automorphisms handout (pdf).
A disconnecting set in G is a set of edges whose removal leaves a disconnected graph.
In a graph G, take two nonadjacent vertices v and w. Then κ(v,w), the connectivity between v and w, is the smallest number of vertices whose removal leaves v and w in different components.
In a graph G, take any two vertices v and w. Then λ(v,w), the edge connectivity between v and w, is the smallest number of edges whose removal leaves v and w in different components.