The Gateway to Computer Science Excellence

+14 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$?

+18 votes

Best answer

+2

Yes, correct.

Extra info: Min value of k is 1 when the graph is star graph where n-1 vertices have degree one and root has degree n-1.

Extra info: Min value of k is 1 when the graph is star graph where n-1 vertices have degree one and root has degree n-1.

0

@Warrior in a tree, degree of a node is equal to the number of sub-trees, right? graph and tree have different definition of degree of a node, isn't it?

0

ISI subjective questions are generally of 10 marks so I guess a general proof for n-ary tree would be better.

@Arjun Sir, trees are generally considered as directed graphs right? Then what about the nodes having 0 degree(leaf nodes)? Why they have not been considered in the answer? 🤔

+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)$

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)$

+2

This is correct Proof for Binary trees not for n-ary trees, but it really helps to understand how it works for any generic trees.Thanks:-)

+7

There is a theorem which says for a tree with at least 2 vertices we have at least 2 pendant vertices.

Since, in a tree of n nodes, we have at least 2 pendant vertices,

the number of vertices left which will surely have the degree more than 1 is

n-2= maximum value of k.

Since, in a tree of n nodes, we have at least 2 pendant vertices,

the number of vertices left which will surely have the degree more than 1 is

n-2= maximum value of k.

0

@tusharp-Be it any tree, max value for k would be $n-2$.

Every tree has atleast 2 pendant vertices.

0 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.

52,217 questions

59,907 answers

201,103 comments

118,146 users