Specify an adjacency-lists representation of the undirected graph given above. [The graph has 5 vertices labelled 1,2,3,4,5. Vertex 2 is at the top; 1 (left) and 3 (right) are in the middle; 5 (bottom-left) and 4 (bottom-right) are at the base. The edges shown are: 1-2, 2-3, 1-3, 1-5, 3-4, 4-5, and the diagonal 3-5.]

GATE 1987 · Discrete Mathematics · Graph Connectivity · easy

Answer: 1 -> {2,3,5}; 2 -> {1,3}; 3 -> {1,2,4,5}; 4 -> {3,5}; 5 -> {1,3,4}

1. List the edges: From the figure: 1-2 and 2-3 (the top triangle's slanted sides), 1-3 (the horizontal middle), 1-5 (left vertical), 3-4 (right vertical), 5-4 (bottom), and 3-5 (the diagonal). That is 7 edges.
2. Build each vertex's neighbour set: Vertex 1 touches edges {1,2},{1,3},{1,5} -> {2,3,5}. Vertex 2 touches {1,2},{2,3} -> {1,3}. Vertex 3 touches {2,3},{1,3},{3,4},{3,5} -> {1,2,4,5}. Vertex 4 touches {3,4},{4,5} -> {3,5}. Vertex 5 touches {1,5},{4,5},{3,5} -> {1,3,4}.
3. Verify with the handshaking lemma: Degrees are 3,2,4,2,3 summing to 14 = 2 x 7, matching the 7 edges. The representation is complete and consistent.