edited by
4,172 views

5 Answers

0 votes
0 votes
We have k Component and given graph is forest so each component has x – 1 edges (where component is tree with x vertices )

suppose we divide vertices v into $x_{1}$ , $x_{2}$ , … , $x_{k}$ => where each $x_{i}$ denote the number of vertices in $i^{th}$  Component

 $x_{1}$ + $x_{2}$ + … + $x_{k}$ = v

 → $x_{1}$ has $x_{1}$ – 1 edges (as each component is a tree)

→ $x_{2}$ has $x_{2}$ – 1 edges

so on

So total number of edges = Sum of all component edges

= ( $x_{1}$ – 1 ) + ( $x_{2}$ – 1 ) + ( $x_{3}$ – 1 ) + … + ( $x_{k}$ – 1 )

= ( $x_{1}$ + $x_{2}$ + … + $x_{k}$) – k

= v – k
Answer:

Related questions

6 votes
6 votes
1 answer
1
3 votes
3 votes
2 answers
2
go_editor asked Jun 24, 2016
3,697 views
Logic family popular for low power dissipationCMOSECLTTLDTL
6 votes
6 votes
4 answers
3
go_editor asked Jun 24, 2016
4,325 views
A problem whose language is recursion is called?Unified problemBoolean functionRecursive problemDecidable
7 votes
7 votes
3 answers
4
go_editor asked Jun 24, 2016
6,112 views
A symbol table of length $152$ is processing $25$ entries at any instant. What is occupation density?$0.164$$127$$8.06$$6.08$