DM-Graphs-Q9

+1 vote

In a tree with 30 vertices, maximum degree 20, there exist at least ---- vertices of degree 1?

(A). 50
(B). 20
(C). 30
(D). 40

asked Jul 12 in Discrete Maths by gbeditor (15,310 points)
reshown Jul 13 by gbeditor

1 Answer

0 votes
Fact one: graph is a tree on nn vertices, it has exactly n−1n−1 edges

Fact two: sum of all degrees is twice number of edges

so there are 29 edges, total degree is 29*2 = 58. now 1 vertex has 20 degree, so remianing degree = 38 and remaining vertex = 29

let number of vertex with degree 1 be 'x', so number of remaining vertex will be (29-x) and they must

be degree 2.

x*1 + (29-x)*2 = 38 , x =20
answered Aug 25 by tsabhineetsingh192 (4,100 points)
@tsabhineetsingh192  bro how did u conclude that remaining vertices (29-x) have degree =2, i am not able to understand
Answer:
...