Why is the number of black nodes in a Red-Black tree at least ⌈h/2⌉?

Question

Why is the number of black nodes in a Red-Black tree at least ⌈h/2⌉ where h is the tree height?

Wikipedia Red-black tree page.

Answer 1

The essence is the third property: a red node can't have a red child (red rule). Take a path from the root to a NIL vertex. This is a chain of father-son $v_1, \ldots, v_h$, with $v_1$ being the root, $h$ being the height of the tree, $v_h$ being a NIL node (a leaf). Just to simplify the explanation, let us distinguish in two cases: $h$ is odd and $h$ is even.

If $h=2m$, suppose by contradiction that there are at least $m+1$ red nodes in the chain. Since if you alternate black and red you fit at most $m$ red nodes, there should be two red nodes one after another, in contradiction with the red rule. We conclude there are at most $m$ red nodes, that is at least $m = h/2$ black nodes.

If $h=2m+1$, suppose there are at least $m+1$ red nodes. The only way you can do this without having two consecutive red nodes is by starting coloring $v_1$ with red, alternating, and finishing $v_h$ with red. But this contradicts the NIL rule, since $v_h$ must be black. We conclude that there are at most $m$ red nodes, that is at least $m+1 = \left \lceil \frac{h}{2} \right \rceil$ nodes.