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?

  • 2
    $\begingroup$ Hi and welcome to the site! Since this is a site that encourages and helps with learning, it is best if you show your own ideas and efforts in solving the question. Can you edit your question to add your thoughts and ideas about it? $\endgroup$ – Bobson Dugnutt Feb 22 '16 at 0:07

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.

  • $\begingroup$ I attempted to use your idea here and got as far as finding out that the number of leaves d = 2n-25 but am not sure how to find n, the number of vertices? $\endgroup$ – Jim Jj Feb 23 '16 at 17:20
  • $\begingroup$ Would it be safe to say that since we've used 5 vertices so far, and every remaining vertex is a leaf, that d = n - 5 and thus n = d + 5? $\endgroup$ – Jim Jj Feb 23 '16 at 17:27
  • $\begingroup$ In all honesty, I am also working on the same problem and got that hint from my prof. What you have so far seems plausible. Could you elaborate on how you found d=2n-25? $\endgroup$ – H.T. Feb 23 '16 at 21:03
  • $\begingroup$ I have come up with a proof: If G is a tree on n vertices then it has n-1 edges. So we let |V(G)| = 2(x_3)+(x_5)+2(x_6)+d(x_1). By the Handshaking: 2(3)+1(5)+2(6)+d=2(n-1). Because the given 5 vertices are not leaves, a=n-5, thus solving for n and then a we get a=15. $\endgroup$ – H.T. Feb 23 '16 at 21:41
  • $\begingroup$ Nice I got pretty much the same thing! Thanks for the original idea on using the Handshaking lemma! Was your prof Cavers by any chance? $\endgroup$ – Jim Jj Feb 23 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.