Suppose that T is a n-vertex tree and let n i denotethe number of vertices of T
ID: 2940233 • Letter: S
Question
Suppose that T is a n-vertex tree and let ni denotethe number of vertices of T that have degree i. Show that thenumber of leaves of T is given by 2 + n3 +2n4 + 3n5 + 4n6 + ... Suggestion: Justify and then use the equations n =n1 + n2 + n3 + ..., 2(n-1) =n1 + 2n2 + 3n3 + ... Suppose that T is a n-vertex tree and let ni denotethe number of vertices of T that have degree i. Show that thenumber of leaves of T is given by 2 + n3 +2n4 + 3n5 + 4n6 + ... Suggestion: Justify and then use the equations n =n1 + n2 + n3 + ..., 2(n-1) =n1 + 2n2 + 3n3 + ...Explanation / Answer
Let us just follow the suggestion. Firstly, if we have indeedproven that n = n1 + n2 + n3+... -----------------(1) 2(n-1) = n1 + 2n2 + 3n3+.... -----------------(2) then are we done? A leaf is a vertex of degree 1, so we are indeedinterested in n1. The formulae above tell us 2n= 2n1 + 2n2 + 2n3 +.....(multiply the first equation by 2) 2n-2 = n1 + 2n2 + 3n3 +.... Subtracting,we get, 2 = n1 - ( n3 +2n4 + 3n5 + ....) and that gives us what we want. So if suffices to prove (1) and (2). (1) is straightforward. Sincethe number of vertices is n, and every vertex has degree 1, or 2 or3, or..... (Importantly, no vertex has degree 0 since the graph isa tree and hence is connected), so n = n1 + n2 + n3 +... For (2), use a similar statement about the edges. We know that sumof degrees of the vertices is a graph is 2(edges in G). Since a tree on n vertices has n-1 edges, the sum of degrees of thevertices of the tree is 2(n-1) giving the LHS of (2). But for the RHS, note that the vertices of degree 1 contribute(n1) (1) to the sum; the vertices of degree 2 contribute(n2) (2) to the sum and so on. Thus, the total contribution from all thevertices is n1 + 2n2 + 3n3+.... as required.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.