How many edges are there in a forest of t-trees containing a total of n…
2013
How many edges are there in a forest of t-trees containing a total of n vertices ?
- A.
n + t
- B.
n – t
- C.
n ∗ t
- D.
nt
Attempted by 278 students.
Show answer & explanation
Correct answer: B
Key idea: A forest of t trees with a total of n vertices can be analyzed by applying the fact that each tree with v vertices has v − 1 edges.
Let the t trees have vertex counts v₁, v₂, …, v_t respectively.
Each tree i has v_i − 1 edges, so the total number of edges is the sum of (v_i − 1) over i = 1 to t.
Compute the sum: sum(v_i − 1) = (sum v_i) − t = n − t.
Answer: The forest has n − t edges.
A video solution is available for this question — log in and enroll to watch it.