Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.
I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).
Could you give me a hint ?