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, 2019 in Discrete Maths by gbeditor (32,710 points) 1 flag
reshown Jul 13, 2019 by gbeditor

1 Answer

+1 vote
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, 2019 by (4,310 points)
@tsabhineetsingh192  bro how did u conclude that remaining vertices (29-x) have degree =2, i am not able to understand
WHY REMAINING VERTEX ARE  OF DEGREE 2.
options  se match hoga, that's why(IMO).
Answer:
...