Finding the number of nodes in a tree with 5 leaves

46 Views Asked by At

Let $ T = \left(V, E\right) $ be a tree with $ 5 $ leaves such that every non-leaf node has a degree of $ 3 $. I want to prove that $ \left|V \setminus L\left(T\right)\right| = 3 $. Here is what I have so far, but I couldn't finish the proof.

$ T $ is a tree and therefore $ \left|E\right| = \left|V\right| - 1$. We know that $ \left|E\right| = \frac{1}{2}\sum_{w \in V} deg_T\left(w\right) $. Let $ x $ be the number of non-leaf nodes. Therefore, $ \left|E\right| = \frac{1}{2}\left(3x + 5\right) = 1.5x + 2.5 $. But I dont't know how to continue from here.

1

There are 1 best solutions below

0
On

You are almost there. $|E| = |V| - 1$ gives you the second equality: $$|E| = x + 5 - 1 = x + 4.$$ Now you can solve for $x$.