# m-ary tree relation between vertices and leaves

A full $$m$$-ary tree with $$n$$ vertices and $$i$$ internal vertices has $$n = m \cdot i + 1$$ vertices and $$l = (m − 1)i + 1$$ leaves.

How can I prove it?

I know that $$m$$-ary tree is a rooted tree such that every internal vertex has no more than $$m$$ children. The tree is called a full $$m$$-ary tree if every internal vertex has exactly $$m$$ children. An $$m$$-ary tree with $$m = 2$$ is called a binary tree.

• What would be the correct relation instead of l=m-i+1? Oct 26, 2021 at 21:58

A vertex is either an internal vertex or a leaf. Since the number of all vertices is $$n$$ while the number of internal nodes is $$i$$, the number of leaves, $$l$$ is $$n-i$$.
Every vertex is identified as a child of an internal node except the root. Since there are $$i$$ internal node, each of them having $$m$$ children, the number of vertices, $$n$$ is $$m\cdot i + 1$$.
Since $$i= n-l$$, we also have $$n = m\cdot (n-l) + 1$$. Or $$(m-1)n = m\cdot l - 1,$$ which is the relation between the number of vertices and the number of leaves in a full $$m$$-ary tree.