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.