As pointed out by Pavel Raykov, the proof of Lemma 2 on page 13 is 
wrong. Below, you find a correct proof. 

We use the notation in the proof of Lemma 2 on page 13. 

======================================================================
Case 1: $n_A + n_B + n_C \leq i-2$. 

In this case, the element of rank $i$ that we are searching for is not 
the root of $T_A$ and it is not in the left subtree of $T_A$. Thus, 
in $T_A$, we can move to the right child of the root. 
======================================================================
Case 2: $n_A + n_B + n_C \geq i-1$. 

In this case, the rank of $r_C$ is at least $n_A + n_B + n_C + 3$, 
which is at least $i+2$, which is larger than $i$. (Note: the "3" 
accounts for the three roots.) 

Thus, the element of rank $i$ that we are searching for is not equal 
to $r_C$ and it is not in the right subtree of $T_C$. Therefore, we 
can move to the left child of the root in $T_C$. 
======================================================================

In some iteration, the child we want to move to does not exist. Then 
we know that the element we are searching for is in the other two 
trees. In these two trees, we use the same approach. Note that 
Cases 1 and 2 also work for two trees, in which case we only have 
$n_A$ and $n_B$. 

During the search in the two trees, in some iteration, the child we 
want to move to does not exist. Then we know that the element we are 
searching for is in the other tree. In this other tree, we can do 
selection by walking down the tree.