Data Structures, Algorithms, & Applications in Java
Chapter 7, Exercise 7

(a)

We can prove this by induction on u. In the induction base, we establish the result for u = 0. When no unions have been performed, each class has exactly one element. Therefore, no class has more than u+1 = 1 element.

In the induction hypothesis, we assume that no class has more than u+1 elements when the number of unions is at most m, where m is an arbitrary natural number.

In the induction step, we must show that no class has more than m+2 elements when the number of unions is m+1. Consider the class A with the largest number of elements. This class has more than one element, and so it is the result of one or more unions starting from singleton classes. Suppose that the last union performed to create A united classes B and C. The maximum number of union operations used to create B and C is m (note that one union is used to unite B and C to create A, leaving m unions for the creation of other classes). Let b be the number of union operations performed to create B. The number used for C is at most m-b. From the induction hypothesis it follows that the number of elements in B is at most b+1 and the number in C is at most m-b+1. Therefore, the number of elements in A is at most b+1+m-b+1 = m+2.

(b)

There are three cases for a union operation: it unites two singleton classes, it unites a singleton class and a nonsingleton class, and it combines two nonsingleton classes. The first case reduces the number of singleton classes by two, the second by one, and the third by zero. Therefore, after u union operations the number of singleton classes is at least n-2u.

(c)

Each union reduces the number of classes by one. Therefore, after n-1 unions, the number of classes is one and no further unions can be done. So u < n.