Directions: Type your solutions into this document and be sure to show all steps for arriving at your solution. Just giving a final number may not receive full credit. Problem 1 For parts (a) and (b), indicate if each of the two graphs are equal. Justify your answer. (a) Figure 1: Left: An undirected graph has 5 vertices. The vertices are arranged in the form of an inverted pentagon. From the top left vertex, moving clockwise, the vertices are labeled: a, b, c, d, and e. Undirected edges, line segments, are between the following vertices: a and b; a and c; b and c; c and d; e and d; and e and c. Figure 2: Right: The adjacency list representation of a graph. The list shows all the vertices, a through e, in a column from top to bottom. The adjacent vertices for each vertex in the column are placed in a row to the right of the corresponding vertex’s cell in the column. An arrow points from each cell in the column to its corresponding row on the right. Data from the list, as follows: Vertex a is adjacent to vertices b and c. Vertex b is adjacent to vertices a and c. Vertex c is adjacent to vertices a, b, d, and e. Vertex d is adjacent to vertices c and e. Vertex e is adjacent to vertices c and d.

The vertex set in both figures is: V = {a, b, c, d, e} Since there are no extra or missing vertices, this matches. • Comparing each vertex’s adjacency list with the edges in Figure 1: – Vertex a: - Adjacency List: {b, c} - Expected Edges: (a, b), (a, c) – Vertex b: - Adjacency List: {a, c} - Expected Edges: (b, a), (b, c) – Vertex c: - Adjacency List: {a, b, d, e} - Expected Edges: (c, a), (c, b), (c, d), (c, e) – Vertex d: - Adjacency List: {c, e} - Expected Edges: (d, c), (d, e) – Vertex e: - Adjacency List: {c, d} - Expected Edges: (e, c), (e, d) • Since every vertex’s adjacency list correctly represents the edges in Figure 1, the two graphs are equal. is this answer correct?