The number of articulation point of the following graph is:
1999
The number of articulation point of the following graph is:
- A.
0
- B.
1
- C.
2
- D.
3
Attempted by 25 students.
Show answer & explanation
Correct answer: D
An articulation point (cut vertex) is a vertex whose removal increases the number of connected components of the graph.
Check each important vertex
Vertex 2: Removing 2 disconnects vertex 4 from the rest of the graph.
⇒ 2 is an articulation point.
Vertex 3: Removing 3 separates the left part {1,2,4} from the right part {5,6,7}.
⇒ 3 is an articulation point.
Vertex 5: Removing 5 disconnects vertices 6 and 7 from the rest of the graph.
⇒ 5 is an articulation point.
Other vertices
Removing 1 does not disconnect the graph because 2 and 3 remain connected.
Removing 4, 6, or 7 only removes a leaf vertex and does not disconnect the remaining graph.
The articulation points are: {2,3,5}
Number of articulation points: 3