The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
628 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$?
asked in Graph Theory by Active (4.3k points)
retagged by | 628 views
+1
Is it n-2 ?
0
see if it is a skewed tree

then n=k,rt?
+1
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

+11 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.$
answered by Active (2.3k points)
selected by
+1
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.
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?
+14 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)$
answered by Active (4.8k points)
edited by
+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:-)
+1

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

+5
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.


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

36,088 questions
43,531 answers
123,704 comments
42,762 users