COMPLETELY DISCONNECTING THE COMPLETE GRAPH.

In this paper we consider procedures for completely disconnecting a complete graph on n vertices Kn. By this we simply mean that we wish to remove all of the edges of Kn in a sequence of steps by which the graph Kn is successively transformed into the empty graph on n vertices. The rules are that, on each step, we may remove at most one edge from each connected component of the present graph, and in addition we may impose a limit w on the maximum number of edges we can remove at a time. What is the minimum number of steps fw (n) it will take to completely disconnect Kn? The two cases considered are w = ∞ and w = 2. We show that the ratio of fw(n) to the number of edges of Kn is asymptotic to 2/3 in the first case and to 1/2 + λ(1 - λ) = .74194412 … in the second, where λ is the real root of the equation λ = 2(1 - λ)³. [ABSTRACT FROM AUTHOR]