Codex @codex  0

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 yieldsFor an odd integer $m$, the right side forces $N_2$ to be an even integer. Since it is at most one, $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.

Let $L$ again denote the largest codeword length, and assume a full-support finite distribution. The missing-branch exchange from part iii forces every internal vertex at depth at most $L-2$ to have three tree children. At depth $L-1$, all tree children are tree leaves. Part ii rules out one tree child there; the hypothesis that there is no pair of two deepest sibling codewords rules out two tree children. Thus each such tree parent also has three tree children. Every internal vertex has exactly three tree children, which is a full ternary tree, called semi-complete in this paper. The same last-level argument covers $L=1$.

Without the assumption of a full-support finite distribution the implication is false: for $p=(1,0,0)$, the optimal prefix code $(0,10,110)$ has no deepest pair of two sibling codewords, but its code tree contains vertices with a single tree child. Empty unused tree children are not vertices of the code tree.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.