= Solution
Assume a <full-support finite distribution>. The preceding structural arguments show that every internal <vertex> has three <tree children>, except possibly one <tree parent> at depth $L-1$ with two <tree children>. Let $N_3$ and $N_2$ count these two kinds of internal <vertex>. Part iv gives $N_2\in\{0,1\}$; no <vertex> has one <tree child>.
A finite <rooted tree> with $m$ <tree leaves> has $m+N_2+N_3-1$ <edges>, while counting outgoing <edges> gives $2N_2+3N_3$. Equating the counts yields
$$
m=1+N_2+2N_3.
$$
For an <odd integer> $m$, the right side forces $N_2$ to be an <even integer>. Since it is at most one, \b[$N_2=0$]. Thus no deepest pair has only two <sibling codewords>, and the optimal <code tree> is a <full ternary tree>. This leaf-count identity also directly proves that a <full ternary tree> has an <odd number> of <tree leaves>.
Again the unrestricted zero-weight version is false: $(0,10,11)$ is an optimal <prefix code> for $p=(1,0,0)$, with <odd integer> $m=3$, but its two deepest <tree leaves> form a two-sibling pair. There is no contradiction with the proof because its <tree root> has only two <tree children>, which the <full-support finite distribution> assumption would forbid above the deepest level.
Back to article page
