= Random branch-set construction of a complete graph minor
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>.
Back to article page
