The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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$?
asked in Graph Theory by Loyal (4.6k points)
retagged by | 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.

2 Answers

+13 votes
Best answer
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)
answered by Boss (5.2k points)
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.
+10 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
answered by Active (2.2k points)
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?

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

33,712 questions
40,255 answers
38,883 users