The GATE Grind

GATE 2014 CS (CS3) – Question 61

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

A forest G has n vertices and k connected components. How many edges does it have?

  1. $\lfloor n/k\rfloor$
  2. $\lceil n/k\rceil$
  3. $n-k$
  4. $n-k+1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $n-k$

Explanation

Each connected component of a forest is a tree. A component with n_ivertices has n_i−1edges; summing over kcomponents givesΣn_i−k=**n−k,C**. Isolated vertices satisfy the same formula with zero edges.