Branch set of a graph minor

A branch set is a nonempty set of vertices inducing a connected graph used to represent one vertex of a graph minor. A $K_t$ graph minor is equivalent to $t$ disjoint branch sets with at least one edge between every pair. Connectedness allows each set to be reduced to a single vertex by edge contractions.

In a dense graph with many common neighbours for every pair of vertices, choose disjoint random small sets. A set is good if few vertices have no neighbour in it. The Markov inequality controls the number of bad sets, and random sampling makes almost every pair of good sets adjacent. Add unused common neighbours to connect each set and to repair the remaining missing adjacencies. If the number of used vertices stays below every common-neighbour count, this constructs disjoint branch sets of a graph minor representing a large complete graph.