2.8k views
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
edited | 2.8k views

Tree with $n$ vertices which means $n-1$ edges.

$n = 10 \therefore \ edges = n - 1 = 9$.

$\therefore$ Sum of degree of all vertices $\leq 2E \leq 2*9 \leq 18$
edited by
it is 18 for sure.

Sum of degrees of all vertices = twice the number of edges = 2e we know,

now e = n-1

here n = 10 given

hence 2e = 2(n-1) = 2*9 = 18
A tree with n vertices can have maximum of n-1 edges.

Now by Handshaking Lemma we know sum of degrees of all vertices <= 2E<=2(n-1)<=2*(10-1)<=18

Ans: 18

Let d1, d2, ...dn be a degree sequence, then

$\sum_{k=1}^{n}$ dk = 2*(n-1) , where n = number of vertices, IFF the given graph is a tree.

So, sum of degrees = 2*(10-1)

= 18

sum of degree=2e

e=9 so 2*9=18.

Use sum of degree theorem to:- for a graph,  total sum of degree is = 2 * total edges
so here the number of nodes=10
so edge (E)=10-1=9
so the sum of degree should be like
sum of degree <=2*E => sum of degree <= 18
–1 vote
I think the answer should be 9. As it is a tree, the degree of a node/vertex is the number of child nodes it has and the parent is not taken into consideration. Thus, Handshaking lemma can not be applied as it is not a graph.

Try arranging the nodes in any way possible the summation of degrees of all the node will equal to (n-1) for a tree with n nodes.