Note on the structure of Kruskal's algorithm

We study the merging process when Kruskal's algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in [0,1] ^d , and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be T(n) on average. On the way to the proof, we obtain similar results for the complete graph and the d-dimensional square lattice with i.i.d. edge weights.