GATE CS 2021 (Forenoon) — Question 51

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMSQ2 marksMedium

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?
  1. A
    Root of \(T\) can never be an articulation point in \(G\).
  2. B
    Root of \(T\) is an articulation point in \(G\) if and only if it has 2 or more children.
  3. C
    A leaf of \(T\) can be an articulation point in \(G\).
  4. 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\).
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group