542 views
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 | 542 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.

let ,  the tree with degree max =2 ,

let , no of intenal nodes whose degree >1 =k

then no of pedent 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) => k = (n-2)
edited
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.
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
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?