GATE CS 1999 Q1.15 — Graphs: Connectivity, Matching, Colouring

An articulation point (or cut vertex) in a connected graph is a vertex whose removal increases the number of connected components (i.e., disconnects the graph).

By analyzing the given graph, we can identify the vertices whose removal disconnects the graph:

• Removing the first cut-vertex (let's denote it as $v_3$) disconnects the leftmost cycle/pendant vertices from the rest of the graph.
• Removing the central cut-vertex (let's denote it as $v_5$) disconnects the left block from the right block.
• Removing the third cut-vertex (let's denote it as $v_7$) disconnects the rightmost cycle/pendant vertices from the rest of the graph.

No other vertex removal disconnects the graph. Thus, there are exactly 3 articulation points.