Let G be a tree with a vertex of degree 5 Prove that G has a

Let G be a tree with a vertex of degree 5. Prove that G has at least 5 vertices of degree 1. (Hint there are at least two ways you can prove this: (i) Consider the graph that results when the vertex of degree 5 is removed. (ii) Write a proof by contradiction and use the Handshaking Theorem.)

Solution

handshaking theorem

sum (deg(v))) =2(E)
let the tree be of n nodes,number of edges is n-1

teh root has degree 5
5+ sumof n-1(deg(v)) =2(n-1)
sumof n-1(deg(v))=2n-7
   teh least degrees are 1 and 2
   this means that there are atleast 5 nodes of degree 1