I am studying for an upcoming Discrete Math exam, and the final section is on trees. I understand the theory, but some of the questions require memorizing several formulas for calculating the number of vertices, internal vertices, and leaves.
The professor mentioned that there are maybe just 2 formulas we should learn and algebraically derive the rest, but I am unsure which 2 I should memorize. Any help would be appreciated!
n vertices has i = (n – 1)/m internal vertices and l = [(m – 1)n + 1]/m leaves i internal vertices has n = mi + 1 vertices and l = (m – 1)i + 1 leaves l leaves has n = (ml – 1)/(m – 1) vertices and i = (l – 1)/(m – 1) internal vertices
Edit: n = vertices m = edges
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 \Rightarrow i=\dfrac{l-1}{m-1}$
and
$n=mi+1 \Rightarrow n=\dfrac{m(l-1)}{m-1}+1=\dfrac{ml-m+m-1}{m-1}=\dfrac{ml-1}{m-1}$