Student name:________________________ Preceptor: __________________________
Grade: ____________________ Grader: ______________________
1. Consider the graphs defined by the following sets of edges:
A. 0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
B. 0-1 0-2 0-3 0-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
C. 0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8
D. 4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7
Which of these graphs are isomorphic to one another?
2. K(n) denotes the graph with n vertices and all n(n-1)/2 edges. Is it possible to draw K(5) in the plane so that no edges cross? What if you draw K(5) on a torus (ie, the surface of a donut): can you avoid crossings then? If yes, draw a picture to explain. Now, remove one edge from K(5) and show by a picture that the resulting graph can be drawn in the plane with no crossings.
What about K(3,3) and K(3,3) minus one edge? Can they both be drawn
in the plane? [ K(n,n) denotes the graph with 2 groups of n vertices each
and all n^2 edges joining them. ]