Meir & Moon [MM70] found that an average number
of random cuts are necessary to destroy a random size-
Cayley tree (to be compared to
cuts for a linear tree).
Under some probabilistic assumptions (cf. Knuth &
Schönage [KS78]), the number of random cuts
is
distributed as the number of UNION operations experienced by a given
element during the implementation of a UNION-FIND algorithm. There is
also an interpretation in terms of hashing tables, that we use to
obtain the limit law of
.