|proof=
Если Так как только черные узлы могут иметь красных детей, то в самом длинном пути от корня до листа красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше <tex>h/2-1</tex> и, по лемме, количество внутренних вершин в дереве
<tex>N \geqslant 2^{h/2}-1</tex>
