Red-Black Tree Proof

Question

I have a question on my final review sheet that says. Prove for n>1, a red-black tree must have at least 1 red node. This makes sense to me since if n is even, the 2 subtrees from the root have different number of nodes therefore there must be at least one red to keep all paths the same black height. Then there is another problem that says the minimum internal nodes for a tree with black-height k is 2^k -1. The proof for that is that if every node was black the complete binary tree, assuming the dummy external leaves are counted, would have height k, and plugging that into the formula 2^h -1 gives us the answer.

My issue is that how can the first proof coincide with the second. How can a tree with more than 1 node have to have at least 1 red node, yet a minimum internal node tree has only black nodes. Can anyone enlighten me please?

Answer 1

The first prove is based on its insertion algorithm which is why there's always a red node. But on the second prove, you actually can build a Red-Black tree consisting only black manually. With the commonly used insertion algorithm, you always get a red at insertion.

I insert this as an answer in case someone has a same problem or know more accurate word to use as an aswer.

Reading material : http://www.geeksforgeeks.org/red-black-tree-set-2-insert/