Finding number of leaves in a tree of 60 nodes in which 10 are of degree 3

Question

I'm kinda stuck with this and can't seem to solve this question.

Let G be a tree with 60 nodes, 10 of those nodes are of degree 3, there are no nodes with a degree larger than 3. How many leaves are in G?

Need to solve in 2 ways. Using finding the number of leaves using prufer code and without using prufer code.

Any hints?

Answer 1

You can use the Handshake Lemma. We have $10(3) + \ell + 2k = 2E$, where $E$ is the number of edges, $\ell$ is the number of leaves, and $k$ is the number of vertices of degree $2$. As $|T| = 60$, we have $10 + k + \ell = 60$. So $k + \ell = 50$. As $\ell$ is even, it follows that $k$ must be even as well.

Given that $T$ is a tree, $T$ has $59$ edges. So $2E = 108$. This simplifies to the system of equations, which you can easily solve:

$x + 2y = 78$
$x + y = 50$