Prove that every thin AVL tree may be converted to red-black tree 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 ?  

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin.   Moreover this node must be red (property of black height).
Example:
Just a remark.

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T_h$ of height $h$ is recursively defined as root with two subtrees $T_{h-1}$ and $T_{h-2}$. Hence the name.

As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T_{h-1}$ and $T_{h-2}$ must have the same black height  in $T_h$, although they differ in height.