retagged by
2,307 views
15 votes
15 votes
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
retagged by

3 Answers

Best answer
19 votes
19 votes
Maximum value of $k$ is $n-2$ which is example of line graph because every tree should contain at least $2$ pendent vertices (i.e vertex with degree $1$). Therefore value of $k$ cannot exceed $n-2.$
selected by
20 votes
20 votes
Let the tree with degree max $=2$ ,

Let , no of internal nodes whose degree $>1 =k$

then no of pendent vertex $= n-k$

now as we know that no of edges in tree $= n-1$

by handshaking theorem ,

sum of degrees of each verteces  $= 2 *$ edges

now , $2*(k)+1*(n-k) = 2*(n-1) \Rightarrow k = (n-2)$
edited by
3 votes
3 votes

Sum of degree = 2 * No. of edges

As in our question we have a tree No. of edges = (n - 1)

So, Sum of degree = 2 *(n - 1)

Now we can see this problem as a pigeon-hole problem. (Each vertex is a hole)

Distributing 2(n-1) pigeons into n holes, such that there are maximum holes with greater than 1 pigeon.

Step1) Add 1 pigeon to each hole. Remaining pigeons to be distributed = 2(n-1) - n = (n - 2).

Step2) Again add 1 pigeon to each hole from the remaining (n-2) pigeons. (By doing so we maximize the number of holes with greater than 1 pigeon). We can do this for (n-2) pigeons and still we will have 2 holes remaining with 1 pigeon each.

So, the maximum value of k = (n-2) where k is the number of nodes with degree greater than 1.

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
jjayantamahata asked Mar 30, 2018
514 views
Let $$f(x,y) = \begin{cases} \dfrac{x^2y}{x^4+y^2}, & \text{ if } (x,y) \neq (0,0) \\ 0 & \text{ if } (x,y) = (0,0)\end{cases}$$Then $\displaystyle{\lim_{(x,y)...
3 votes
3 votes
4 answers
3
jjayantamahata asked Mar 30, 2018
1,433 views
If $a,b,c$ and $d$ satisfy the equations$a+7b+3c+5d =16$$8a+4b+6c+2d = -16$$2a+6b+4c+8d = 16$$5a+3b+7c+d= -16$Then $(a+d)(b+c)$ equals$-4$$0$$16$$-16$
19 votes
19 votes
4 answers
4
abhi18459 asked May 8, 2016
1,710 views
A palindrome is a sequence of digits which reads the same backward or forward. For example, $7447$, $1001$ are palindromes, but $7455$, $1201$ are not palindromes. How ma...