Math 137A

Test One

Spring 2023

1. Are the graphs below isomorphic? Justify your answer.

2. (a) Draw two different (non-isomorphic) simple cubic graphs on 6 vertices. (Explain why they are non-isomorphic!)

(b) Draw all simple cubic graphs on 7 vertices (Justify why your list is complete).

(c) Draw all simple cubic disconnected graphs with 8 vertices. (Justify why your list is complete).

3. Suppose that T is a tree with degree sequence (5, 5, 3, 3, 2, 2, 1, . . . , 1). How many vertices does this tree have?

4. Apply Kruskal’s algorithm to the graph below to find a minimum spanning tree (List out the edges you are choosing as an ordered list, and trace out the tree on top of the given graph.)

5. Construct the tree on vertex set {1, 2, . . . , 8} with Prufer code

3, 4, 8, 8, 1, 2.