SCIENTIST B CPCB 2023 CSE

Question

Consider a graph with n vertices that is a collection of k disjoint trees, where 𝑛 > 𝑘 > 1 . How many edges does this graph have?

(A) n-1 (B) k (n-1) (C) n-k (D) n-k-1

Answer 1

given that, 

in a graph there are

n vertices , and k disjoint trees 

first approach : directly take examples and find .

second approach : find by using properties of graph and tree

concept: “in a tree having V vertices we know number of edges is V-1 as tree is an connected acyclic graph” 

so, there are k connected components in given graph where each connected component is a tree,

let $n_{1}$,$n_{2}$,$n_{3}$……….$n_{k}$ be number of vertices in first connected component,second connected component…….…...$k_{th}$ connected component respectively.

as each connected component is a tree hence number of edges in first connected component, second connected component,…………...$k_{th}$ will be 

$n_{1}-1$, $n_{2}-1$, $n_{3}-1$, ………………..,$n_{k}-1$  respectively.

 

so total number of edges in graph = ($n_{1}-1)$+ ($n_{2}-1)$+($n_{3}-1$) +………………..+ ($n_{k}-1$)

                                                             = ($n_{1}+$ $n_{2}+$$n_{3}$ ………………..$n_{k}$) -1-1-1-1…….k times

                                                             = n-k  

Answer 2

option (a) is correct = (n-1)