Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
|proof=
Возьмем дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код, и преобразуем для алфавита <tex>C</tex>. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> являются листьями - листья с общим родительским узлом, причем в новом дереве эти листья находятся находящиеся на максимальной глубине.
Пусть символы <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые имеют общий родительский узел и находятся на максимальной глубине дерева <tex>T</tex>.Предположим, что <tex>f[a] \le f[b]</tex> и <tex>f[x] \le f[y]</tex>. Так как <tex>f[x]</tex> и <tex>f[y]</tex> - две наименьшие частоты, а <tex>f[a]</tex> и <tex>f[b]</tex> - две произвольные частоты, то выполняются отношения <tex>f[x] \le f[a]</tex> и <tex>f[y] \le f[b]</tex>. Пусть дерево <tex>T'</tex> - дерево, полученное из <tex>T</tex> путем перестановки листьев <tex>a</tex> и <tex>x</tex>, а дерево <tex>T''</tex> - дерево полученное из <tex>T'</tex> перестановкой листьев <tex>b</tex> и <tex>y</tex>. Разность стоимостей деревьев <tex>T</tex> и <tex>T'</tex> равна:
Предположим без потери общности, что <tex>B(T) - B(T') = \sum\limits_{c \in C} f[a] (c)d_T(c) - \sum\limits_{c \le in C} f(c)d_{T'}(c) = (f[ba]</tex> и <tex>- f[x] \le f[y])(d_T(a) - d_T(x)),</tex>.
Поскольку что больше либо равно <tex>f[x]0</tex> и <tex>f[y]</tex> — две самые маленькие частоты (в указанном порядке), так как величины <tex>f[a]</tex> и <tex>- f[bx]</tex> — две произвольные частоты, то выполняются соотношения и <tex>f[d_T(a) - d_T(x] \le f[a])</tex> и неотрицательны. Величина <tex>f[ya] \le - f[bx]</tex>. В результате перестановки в дереве неотрицательна, потому что <tex>Tx</tex> листьев - лист с минимальной частотой, а величина <tex>d_T(a</tex> и <tex>) - d_T(x)</tex> получается дерево является неотрицательной, так как лист <tex>T'a</tex>, а при последующей перестановке находится на максимальной глубине в дереве <tex>T'</tex> . Точно так же перестановка листьев <tex>by</tex> и <tex>yb</tex> получается дерево не будет приводить к увеличению стоимости. Таким образом, разность <tex>B(T') - B(T'')</tex>тоже будет неотрицательной. Разность стоимостей деревьев Т и Т" равна
<tex>B(T) - B(T') = \sum\limits_{c \in C} f(c)d_T(C) - \sum\limits_{c \in C} f(c)d_{T'}(C)= \\ \\=(f[a] - f[x])(d_T(a) - d_T(x)) \ge 0 ,</tex> поскольку величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательна, потому что х — лист с минимальной частотой, величина <tex>d_T(a) - d_T(x)</tex> неотрицательна, потому что <tex>a</tex> — лист на максимальной глубине в дереве <tex>T</tex>. Аналогично, перестановка листьев <tex>y</tex> и <tex>b</tex> не приведет к увеличению стоимости, поэтому величина <tex>B(T') - B(T'')</tex> неотрицательна. Таким образом, выполняется неравенство <tex>B(T'') \le B(T'')</tex>. С другой стороны, и поскольку <tex>T</tex> — - оптимальное дерево, то поэтому должно также выполняться неравенство <tex>B(T'') \le B(T'')</tex>, откуда . Отсюда следует, что <tex>B(T') = B(T'')</tex>. Таким образомЗначит, <tex>T''</tex> — - дерево, представляющее оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> — находящиеся на максимальной глубине дочерние листья одного и того же узлаимеют одинаковую максимальную длину, что и доказывает лемму.
}}
