A quadrivalent tree is a tree where each vertex has degree 1 or 4.
I was recently given this problem, and have searched online and could not find anything to help me start this:
If a quadrivalent tree has m vertices of degree 4, how many vertices of degree 1 does it have? Prove your answer.
My initial response was to draw out an example of what I think would be the only possible way to maximize a tree given this constraint (without implementing forests).
After doing so, I got a tree on 27 vertices, with 9 vertices of degree 4 and 18 of degree 1. How would I begin to structure a proof here?
As always, thank you for any insight.
Gathering data for $m=1,2,3,4$ should suggest a very simple formula, but it’s also possible to work out the answer without those data. Suppose that $T$ is a quadrivalent tree with $m$ vertices of degree $4$ and $\ell$ leaves. Then the sum of the degrees of the vertices of $T$ is $4m+\ell$, and you know that this is twice the number of edges. Since $T$ is a tree, you also know that it has $m+\ell-1$ edges. Now solve for $\ell$ in terms of $m$.