See below for an example algorithm for finding minimum cut using randomization. The running time of the HCS clustering algorithm is bounded by × f(n, m). f(n, m) is the time complexity of computing a minimum cut in a graph with n vertices and m edges, and is the number of clusters found. In many applications N « n. For fast algorithms for finding a minimum cut in an unweighted graph:   The clusters produced by the HCS clustering algorithm possess several properties, which can demonstrate the homogeneity and separation of the solution. Theorem 1 The diameter of every highly connected graph is at most two. "Proof:" Let n=|G|. If G has a vertex x with degree <= n/2, then G has a minimum cut (that isolates x) with edges <= n/2, so G is not highly connected. So if G is highly connected, every vertex has degree >= n/2. There is a famous theorem in graph theory that says that if every vertex has degree >= n/2, then the diameter of G (the longest path between any two nodes) <= 2. Theorem 2 (a) The number of edges in a highly connected graph is quadratic. (b) The number of edges removed by each iteration of the HCS algorithm is at most linear. "Proof:" (a) From Theorem 1 we know that every vertex has degree >= n/2. Therefore, the number of edges in a highly connected graph must be at least (n × n/2)/2, where we sum the degrees of each vertex and divide by 2. (b) By definition, each iteration removes a minimum cut with <= n/2 edges. Theorems 1 and 2a provide a strong indication of a final cluster's homogeneity. Doing better approaches the case where all vertices of a cluster are connected, which is both too stringent and also NP-hard. Theorem 2b indicates separation since any two final clusters C1 and C2 would not have been separated unless there were at most O(C1+C2) edges between them (contrast with the quadratic edges within clusters). Singletons adoption: Elements left as singletons by the initial clustering process can be "adopted" by clusters based on similarity to the cluster. If the maximum number of neighbors to a specific cluster is large enough, then it can be added to that cluster. Removing Low Degree Vertices: When the input graph has vertices with low degrees, it is not worthy to run the algorithm since it is computationally expensive and not informative.