GATE Computer Science (CS) 2021 Shift 1 Solved Paper

Question : 51 of 65

Marks: +1, -0

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 T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
Root of T is an articulation point in G if and only if it has 2 or more children.
Root of T can never be an articulation point in G.
A leaf of T can be an articulation point in G.

Validate

Go to Question:

Prev Question

Next Question