Computer Sciences > GATE 2021 SET-1 > Graph Theory
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 options is/are correct?
A
Root of T can never be an articulation point in G.
B
Root of T is an articulation point in G if and only if it has 2 or more children.
C
A leaf of T can be an articulation point in G.
D
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.

Correct : b, d

Similar Questions

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represen...
#14 MCQ
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected co...
#18 MCQ
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, a...
#91 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: