GATE CS 2021 Set 1 — Question 51
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0MediumArticulation Points & BridgesGraph AlgorithmsAlgorithms
Algorithms → Graph Algorithms → Articulation Points & Bridges
Last updated
Question
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let be a DFS tree obtained by doing DFS in a connected undirected graph . Which of the following options is/are correct?
Let be a DFS tree obtained by doing DFS in a connected undirected graph . Which of the following options is/are correct?
Correct answer
(B) Root of T is an articulation point in G if and only if it has 2 or more children.
Solution
Standard properties of DFS trees in undirected graphs:
(A) False. The root is an articulation point if it has at least two children in the DFS tree.
(B) True. This is a well-known property: the root of a DFS tree is an articulation point iff it has more than one child.
(C) False. A leaf in a DFS tree of an undirected graph can never be an articulation point because all edges are either tree edges or back edges, and removing a leaf cannot disconnect the graph.
(D) False. While is an articulation point, it doesn't necessarily separate all its descendants from its ancestors. It only separates descendants in subtrees that have no back-edges to ancestors of . If is in a subtree that has a back-edge to , then there is a path from to not passing through .
(A) False. The root is an articulation point if it has at least two children in the DFS tree.
(B) True. This is a well-known property: the root of a DFS tree is an articulation point iff it has more than one child.
(C) False. A leaf in a DFS tree of an undirected graph can never be an articulation point because all edges are either tree edges or back edges, and removing a leaf cannot disconnect the graph.
(D) False. While is an articulation point, it doesn't necessarily separate all its descendants from its ancestors. It only separates descendants in subtrees that have no back-edges to ancestors of . If is in a subtree that has a back-edge to , then there is a path from to not passing through .
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graph Algorithms
2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q24Consider the following functions, where is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array . Suppose the merge sort algorithm is…2026 Set 2 Q37Let be a weighted directed acyclic graph with edges and vertices. Given and a…