Graph minor ($H\preccurlyeq G$)

A graph minor is obtained by deleting vertices, deleting edges, and performing edge contractions. Equivalently, its vertices can be represented by disjoint nonempty connected sets of vertices in the original graph, with an edge joining two sets whenever the corresponding vertices are adjacent. These are branch sets of a graph minor.

The complete graph minor density threshold isThe density here is edge count divided by order, half the average degree of a vertex. For large $t$, this threshold has order $t\sqrt{\log t}$, with the logarithm taken to base $e$.

For each positive integer $k$, a nonempty graph satisfying $e(G)\ge 11k|G|$ has a graph minor $H$ satisfyingThe density hypothesis is a lower bound. Reversing its inequality would be false for an edgeless graph. This auxiliary lemma can be used to establish a $7t\sqrt{\log t}$ upper bound for the complete graph minor density threshold.

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.

Contracting an edge $uv$ identifies its endpoints, then removes loops and duplicate edges to produce a simple graph. It reduces the edge count by exactly $1+|N(u)\cap N(v)|$: one for $uv$, and one for each common neighbour.