The number of articulation points of the following graph is. [The graph has 7 vertices labelled 1-7. Edges: 1-2, 1-3, 2-3 (a triangle), 2-4, 3-5, 5-6, 5-7.] A. 0 B. 1 C. 2 D. 3

GATE 1999 · Discrete Mathematics · Graph Connectivity · medium

Answer: Number of articulation points = 3 => option D

1. Test the bridge endpoints 3 and 5: Edge 3-5 is the only link between the left block {1,2,3,4} and the right block {5,6,7}. Removing vertex 3 splits off {5,6,7}; removing vertex 5 cuts off leaves 6 and 7. Both deletions increase the number of components, so 3 and 5 are articulation points.
2. Test vertex 2: Vertex 4 hangs off vertex 2 only. Deleting vertex 2 isolates vertex 4 from the rest of the graph, increasing the component count, so vertex 2 is an articulation point.
3. Rule out the rest: Vertices 4, 6, 7 have degree 1, so removing any of them leaves the remainder connected. Vertex 1 sits inside the triangle 1-2-3; removing it still leaves 2-3 connected and everything else intact. None of these is a cut vertex.
4. Count: Exactly three vertices, 2, 3 and 5, are articulation points. The count is 3, which is option D.