In a depth-first traversal of a graph G with n vertices, k edges are marked as…

GATE · 2005 · IT

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

  1. A.

    k

  2. B.

    k + 1

  3. C.

    n - k - 1

  4. D.

    n - k

Attempted by 302 students.

Show answer

Correct answer: D

The worked solution is available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…