We have Union-Find-Structure consists of $n$ trees, which have exactly one element. Let $\sigma$ be a sequence of Union-Find-operations, so that all $n$ elements are in one tree with root $v$.
Determine the minimum number of children with root $v$.
Idea:
Obviously the number of children of $v$ is dependent of $\sigma$. So I have tried many examples and I pretty sure that we can say that the minimum number of children has to be $ \lceil log_2(n)\rceil$. But how can I prove this? Maybe induction with $n$?
Remark:
Union : always attaches the taller tree to the root of the smaller tree.
Find($x$) : follows the chain of parent pointers from $x$ up the tree until it reaches a root element, whose parent is itself. for time saving we take $x$ and every node until we reach the root element and make these elements to children of the root element. I hope my description is clear.
Case 1: The shorter tree always attaches to the root of the taller tree.
The root can have just two children for arbitrarily large $n$.
Proof: The tree in figure 1 can be built with a series of union-find operations and arbitrarily many leaves can be added. The trees in figures 1 and 2 can be joined to make figure 3, whose root has two children.
Case 2: The tree with fewer nodes always attaches to the tree with more nodes.
The root has at least $\lceil \log_2(n)\rceil$ children.
Proof is by induction on $n$. Consider the last union required to connect all the elements. In this union, the larger tree has at least $\lceil \frac{n}{2} \rceil$ nodes and its root therefore has at least $\left\lceil \log_2(\lceil \frac{n}2 \rceil)\right\rceil$ children. Adjoining the smaller tree adds an extra child to the root of the larger tree and it can be shown that $\left\lceil \log_2(\lceil \frac{n}2 \rceil)\right\rceil+1 = \lceil \log_2(n)\rceil $.
In fact, this lower bound is exact. To prove this, it suffices to find a construction with $2^k$ nodes where the root has $k$ children (the case where the number of nodes is not a power of two follows because the minimum number of children is a monotonically increasing function of $n$). First, pair up all the nodes into $2^{k-1}$ pairs. Then pair up all of the pairs into $2^{k-2}$ trees with four nodes per tree. Carry on until all of the nodes are connected. It is easy to see that at each pairing the number of children per root increases by one.
Case 3:Taller tree always attaches to root of shorter tree.
Case 4:Tree with more nodes always attaches to tree with fewer nodes.
Case 5: Trees can be attached in any order.
In cases 3,4 and 5, it is possible to create a path by sequentially adjoining nodes. Hence the root can have just one child.