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$?
in Graph Theory by Active
retagged by | 1.1k views
Is it n-2 ?
see if it is a skewed tree

then n=k,rt?
If it is a skewed tree then k can be at Max n-2 because end vertices will have degree 1 only and n-2 vertices will have degree 2.

3 Answers

+18 votes
Best answer
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.$
by Active
selected by
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.
@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?

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)$
by Active
edited by
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:-)

Degree of a node in the tree is equal to the number of sub-trees of that node, right?

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.

@Ayush Upadhyaya for full binary tree it will be 

$(2^{h+1} - 1) - \frac{n}{2}$



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

Every tree has atleast 2 pendant vertices.

Isn't the question asking for the number of internal nodes?
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.

by Active
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
118,146 users