DM-Graphs-Q11

+1 vote

S1: A tree with n vertices which has no vertices of degree 2 must have at least (n+2)/2 leaves

S2: The number of trees on 5 labelled vertices is 125.

Which of the following statements is true?

(A). Only S1

(B). Only S2

(C). Only S1 and S2

(D). None of the above

asked Jul 12, 2019 in Discrete Maths by gbeditor (24,360 points)
reshown Jul 13, 2019 by gbeditor

1 Answer

0 votes

S1: it is true.

S2: According to Cayley's formula for counting spanning trees, for a complete graph Kn,  
T(Kn)= n^{n-2}  where n is the number of vertices.

\implies T(k_{5}}) = 5^{3} = 125

(C). Only S1 and S2

answered Jul 14, 2019 by lakshmanpro20 (6,350 points)
edited Jul 15, 2019 by lakshmanpro20
lakshman bro, how S1 is false....S1 say- "must have ATLEAST (n+2)/2 leave"
for both above tree, this statement satisfies.
both are true
@tshimanshukashyap1122 ,in general trees possible on 5  labelled vertices would cover all type of trees ,so the no. of binary trees possible on 5 labelled vertices are way more than 125 ,then how S2 is correct?
Answer:
...