2,159 views
4 votes
4 votes

Q.A tree has n2 vertices of degree 2,n3 vertices of degree 3.....and nk vertices of degree k.How many vertices of degree 1 does it have ?

a)n2+2n4+3n5+.......+(k-2)nk+1

b)n2+2n3+3n4+.......+(k-1)nk

c)n3+2n4+3n5+.......+(k-2)nk+2

d)None of the above

2 Answers

Best answer
8 votes
8 votes

If we sum up all the degrees (i.e degrees of all the vertices) we will get twice the number of edges. That is the degree sum formula consequence of the handshaking lemma. https://en.wikipedia.org/wiki/Handshaking_lemma

We have vertices with degree $k$ = $n_k$

Summing up gives:

$n_1 + 2n_2 + 3n_3 + . . . + kn_k = 2e$

Here $e$ is the total number of edges. Given the graph is a tree, so we have:

$e = N - 1$

where $N$ is the total number of vertices and:

$N = n_1 + n_2 + ...+ n_k$

so,

$\implies n_1 + 2n_2 + 3n_3 + . . . + kn_k = 2(n_1 + n_2 + ...+ n_k - 1)$

rearranging,

$\implies n_1 + 2n_2 + 3n_3 + . . . + kn_k = 2n_1 + 2n_2 + ...+ 2n_k - 2$

$\implies n_1 + (2-2)n_2 + (3-2)n_3 + . . . + (k-2)n_k + 2 = 2n_1$

$\implies n_1 = n_3 + 2n_4 + 3n_5 +. . . + (k-2)n_k + 2$

There we get it, $n_1$ is the number of vertices with degree = 1.

selected by
0 votes
0 votes
according to handshaking theorem

2|E|=sum of degree of vertices, since it is tree therefore |E|=no. of vertices-1,

let n = number of vertices of degree 1

2{n+n2+n3+....+nk - 1} = n+2n2+3n3+....+knk

on solving you will get option (c)

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
2 answers
2
gagan55 asked Jul 3, 2023
452 views
Consider a complete graph with size 2016. Suppose after deletion of 2 vertices from the above graph, the modified graph have x number of edges and y number of vertices. F...
0 votes
0 votes
1 answer
3
Çșȇ ʛấẗẻ asked Jul 3, 2023
471 views
Prove that following graph does not have Hamiltonian cycle.
0 votes
0 votes
1 answer
4
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??