Aquivalence of q exact tree

111 Views Asked by At

We have the following definition of a q exact tree

A tree $T$ is called $q$ exact if all of it`s interior nodes have q children.
Proof the following : A tree $T$ is $q$ exact if and only if $q-1$ divides $b-1$ where $b$ is the number of leaf nodes

The first direction is very simple since $T$ is q exact and the number of leaves is therefore $q^h -1$ which is divisible by $q-1$.

However, if $q-1$ divides $b-1$ then $b= (q-1)*k+1$ but I don`t know how to follow that $T$ is q exact from that

Would appreciate any help

1

There are 1 best solutions below

0
On

That's because it's false. For instance, if $q = 2$, the condition is that 1 divides the number of leaves minus one, which is obviously true for any tree, not just full binary trees. If $q = 3$, the condition is that $ 2 \mid b - 1$, or equivalently that the number of leaves is odd, which is also true for many trees which are not 3-exact.