retagged by
18,661 views
38 votes
38 votes
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
retagged by

7 Answers

Best answer
52 votes
52 votes
Tree with $n$ vertices which means $n-1$ edges.

$n = 10 \therefore \ \text{edges} = n - 1 = 9$.

$\therefore$ Sum of degree of all vertices $\leq 2E \leq 2*9 \leq 18$

Answer is $18$
edited by
12 votes
12 votes
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
8 votes
8 votes

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

4 votes
4 votes
sum of degree=2e

e=9 so 2*9=18.

18 is the answer.
Answer:

Related questions

33 votes
33 votes
10 answers
1
Arjun asked Feb 14, 2017
16,620 views
Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are:Note: The height of a tree with a single node is $0$.$4$ and $15$ res...
50 votes
50 votes
9 answers
2
go_editor asked Sep 28, 2014
16,248 views
Consider the following rooted tree with the vertex labeled $P$ as the root:The order in which the nodes are visited during an in-order traversal of the tree is$SQPTRWUV$$...
2 votes
2 votes
3 answers
3
Arjun asked Oct 10, 2016
590 views
Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____