What is the smallest number of leaves in a tree with two vertices of degree 3, one vertex of degree 5 and two vertices of degree 6?
I've come up with what I think is the correct drawing containing 15 leaves, but the solution also requires a proof of why this is the smallest possible number. I'm not sure where to start on the proof, although I believe it might involve the fact that the number of edges in a tree is one less than the number of vertices?
Best Answer
I know that we can use the Handshaking lemma to find the lower bound of number of leaves (aka number of vertices of degree 1).
Something like (n-1)= a(x_1)+b(x_2)+c(x_3)+... Where: a, b, c are real numbers, x_i is the vertex with degree i, n is the number of vertices, n-1 is the number of edges.
Thus for this question: (n-1)= 2(x_3)+(x_5)+2(x_6)+d(x_1)
Find the lower bound for d.