I was reading the chapter 21 of the book Introduction to Algorithms (3rd edition) by CLRS and there's the following lemma regarding the union-find data structure with union by rank and path compression:Lemma 21.4For all nodes $x$, we have $x.rank \leq x.p.rank$, with strict inequality if $x \neq x.p$. The value of $x.rank$ is initially $0$ and increases through time until $x \neq x.p$; from then on, $x.rank$ does not change. The value of $x.p.rank$ monotonically increases over time.They give us the following hint:The proof is a straightforward induction on the number of operations, using the implementations of MAKE-SET, UNION, and FIND-SET that appear in Section 21.3.You can find here the same implementations for a union-find data structure which supports union by rank and path compression.I've a few thoughts and ideas, but I'm not able to produce a formal proof.My ideas are the following.The base case is when we do just one operation, i.e. we just call make-set on $x$, i.e. make-set(x). In this function, we set $x.rank = 0$. So, this proves that initially the rank of $x$ (for any $x$) is $0$.We know that the only operation that can change the rank of $x$ (for any $x$) is the union operation. The rank of a node $x$ is changed only when it's a representative of a set and its rank is equal to the rank of the representative of a set of equal size (with which we're merging). Moreover, we have arbitrarily decided that we're going to append the tree of $y$ to $x$ (every time in the next reasonings).We can observe it from this pseudo-code:function Union(x, y)    xRoot := Find(x)    yRoot := Find(y)    if xRoot == yRoot        return    // x and y are not already in same set. Merge them.    if xRoot.rank < yRoot.rank        xRoot.parent := yRoot    else if xRoot.rank > yRoot.rank        yRoot.parent := xRoot    else        yRoot.parent := xRoot        xRoot.rank := xRoot.rank + 1Suppose now that we've only done make-set operations. So, we only have sets of size 1. Suppose we do union(x, y) and we choose to append the root of $y$ to the root of $x$ whenever their representative have equal rank. So the result would be $x.rank = 1$ and $y.rank = 0$. Now suppose we have sets of size greater or equal to $2$. Suppose that we unite two sets of size 2 (the other cases do not change the rank), the previous set containing $x$ and $y$ and another set containing $z$ and $w$, where $z$ is the representative, i.e. its rank is $1$. We're going to append the tree of $z$ to $x$, so $x.rank = 2$, $y.rank = 0$, $z.rank = 1$ and $w.rank = 0$. It seems that if we keep on doing this, we always have that the rank of a parent is always greater than the rank of its children, because we never append a badly constructed tree to the representative of another tree. But I'm not able to prove it formally and clearly (by induction and using the hint they are giving me).Of course, if $x = x.p$, then $x.rank = x.p.rank$ (not a proof, but if x.p is the same object as x, then x.rank must be equal to x.p.rank).Also the find-set operation, which changes also the data structure, because it does path compression. But clearly the find-set operation appends nodes with lower rank to the root... But I should prove it formally!
For all nodes $x$, we have $x.rank \leq x.p.rank$, with strict inequality if $x \neq x.p$
algorithms;data structures;union find