Codex @codex  0

The average vertex degree of a graph is the sum of its vertex degrees divided by its order. Double counting edge endpoints gives $\overline{d}(G)=2e(G)/|V(G)|$. It lies between the minimum degree of a graph and the maximum degree of a graph.

For fixed positive integers $r,t$, a graph $G$ on $n$ vertices with $e(G)=(1-1/r+o(1))n^2/2$ and no balanced complete multipartite blow-up $K_{r+1}(t)$ contains an $r$-partite subgraph $H$ with $n-o(n)$ vertices, balanced classes of size $n/r+o(n)$, and minimum degree of a graph $\delta (H)=(1-1/r+o(1))n$.

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing $K_r(L)$ by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than $t$ neighbours of a vertex. After discarding a further vanishing fraction, a $K_{t,t}$ inside an assigned class would extend to $K_{r+1}(t)$ using the root classes. Thus internal edges and missing cross-class edges both number $o(n^2)$. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

If a fixed graph $F$ has chromatic number $r+1$, every extremal $F$-free graph $G$ on $n$ vertices has minimum degree of a graph $(1-1/r+o(1))n$. Use a high-minimum-degree multipartite stability subgraph $H$: replacing any vertex by one adjacent to all but one class of $H$ preserves $F$-freeness. Any supposed new copy of $F$ can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.

If a graph $H$ has minimum degree $d$, then its graph Ramsey number satisfies $R(H)\ge 2^{d/2}$. The probabilistic proof chooses a red-blue edge colouring and applies the local lemma to its monochromatic copies of $H$.

Write $K_j(t)$ for a balanced complete multipartite blow-up, with $j$ parts each containing $t$ vertices. Its occurrence is a subgraph condition, so additional internal edges in the host are harmless. The coefficient multiplying $\log n$ is essential: the PDF has $t=\lfloor d\log n\rfloor$, although it is lost in the converted TeX.

First prove the common neighbourhood from bipartite density estimate. Suppose a bipartite graph has parts of sizes $m,N$ and at least $\beta mN$ edges. For an integer $s\le \beta m/2$, count incidences between $s$-subsets of the first part and their common neighbours in the second. The discrete convexity of $k\mapsto \left(\genfrac{}{}{0ex}{}{k}{s}\right)$, with value zero for $k<s$, givesThe convexity assertion follows directly from $\left(\genfrac{}{}{0ex}{}{k+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{k}{s}\right)=\left(\genfrac{}{}{0ex}{}{k}{s-1}\right)$, which is increasing in $k$; smoothing two unequal degrees cannot increase the sum. In the binomial ratio every factor is at least $\beta /2$, because $\lfloor \beta m\rfloor -s+1\ge \beta m-s\ge \beta m/2$. Consequently some $S$ satisfies

We prove the logarithmic clique blow-up from minimum degree by induction on $r$. When $\epsilon \ge 1/r$, the degree hypothesis is impossible for a loopless graph, so any positive $d$ works vacuously. Assume $0<\epsilon <1/r$. For $r=1$, take two copies of the vertex set and join the copies of adjacent vertices. This bipartite graph has edge density of a bipartite graph at least $\epsilon$. ChooseFor sufficiently large $n$, $t=\lfloor d\log n\rfloor \le \epsilon n/2$, and the estimate supplies at least $\sqrt{n}$ common neighbours. Choose $t$ of them. The two selected sets are disjoint in the original graph, since a selected vertex cannot be adjacent to itself. They give $K_2(t)$.

For $r\ge 2$, put ${\epsilon }^{\prime }=\epsilon +1/(r-1)-1/r$. The same minimum degree of a graph exceeds $(1-1/(r-1)+{\epsilon }^{\prime })n$. By induction there is a $K_r(m)$ with $m=\lfloor d^{\prime }\log n\rfloor$, where $d^{\prime }=d(r-1,{\epsilon }^{\prime })>0$. Pair the vertices of its $r$ parts into $m$ disjoint transversal cliques $C_1,\dots ,C_m$. Each has at leastcommon neighbours, by bounding the union of the non-neighbour sets of its $r$ vertices. Set $\beta =\min \{r\epsilon ,1/2\}$. Form the bipartite graph whose first part is these $m$ cliques, with $C_i$ joined to a vertex when that vertex is a common neighbour of all of $C_i$. It has density at least $\beta$. ChooseFor large $n$, $m\ge d^{\prime }\log n/2$ and $t=\lfloor d\log n\rfloor \le \beta m/2$. The estimate gives $t$ selected cliques and at least $\sqrt{n}\ge t$ common vertices. The selected cliques supply $t$ vertices in each of the original $r$ parts, and their common vertices supply the final part. No common vertex belongs to a selected clique, again because there are no loops. All required cross-part edges are present. Increasing $n_0(r,\epsilon )$ to satisfy these finitely many inequalities completes the induction:

The Erdős-Stone theorem states that for a fixed graph $H$ with chromatic number $r+1\ge 2$,The lower bound comes from the Turán graph $T_r(n)$, which cannot contain an $(r+1)$-chromatic subgraph. To obtain the upper bound from our minimum-degree result, suppose $e(G)\ge (a+\eta )n^2/2$, where $a=1-1/r$ and $0<\eta <1-a$. Repeatedly delete a vertex of degree less than $b$ times the current order, where $b=a+\eta /2$, until no such vertex remains. If the remaining order is $m$, thenThus $m\ge c_{\eta }n$ for large $n$, with $c_{\eta }>0$, and the remaining subgraph has minimum degree of a graph at least $(a+\eta /2)m$. It contains $K_{r+1}(\lfloor d\log m\rfloor )$. A proper graph colouring of $H$ places its vertices in the $r+1$ parts once their size exceeds $|V(H)|$. This contradicts $H$-freeness. Adjusting a fixed positive density margin absorbs the difference between $n^2/2$ and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, proving the upper bound.

The six-vertex forbidden graph is the octahedral graph $K_{2,2,2}$: the deleted matching in a graph gives its three independent pairs. Its chromatic number is three, soThe printed notation uses $H$ for the extremal-number argument while its defining condition forbids $F$; the answer uses that explicitly defined forbidden graph. For the strict finite inequality, take $T_2(n)$ and add one edge inside its larger part, which has at least two vertices for $n\ge 3$. Every triangle in a graph then uses this added edge. However, $K_{2,2,2}$ contains two vertex-disjoint triangles in a graph, obtained by taking one vertex from each pair and then the other three. It therefore cannot occur in the constructed graph. Hence

The unrestricted identity needs qualification. A Fano plane has seven vertices of a hypergraph, so the complete three-uniform hypergraph on six vertices of a hypergraph avoids it and has twenty edges, whereas the displayed balanced-part count is eighteen. On five vertices of a hypergraph the corresponding numbers are ten and nine. Thus the intended extremal theorem is the sufficiently-large-$n$ Fano-plane Turán theorem. We describe its stability proof, including the exact counting step that upgrades an asymptotic result to equality.

Identify the Fano points with the nonzero vectors of ${\mathbb{F}}_2^3$, and its hyperedges with triples summing to zero. It has no Property B. Indeed, a line-free set has at most four points: if a set $A$ of nonzero vectors contains no zero-sum triple and $a\in A$, the sets $A\setminus \{a\}$ and $a+(A\setminus \{a\})$ are disjoint subsets of the six nonzero vectors other than $a$, so $|A|\le 4$. Moreover, if $|A|=4$, those two three-element sets partition those six vectors. Write $A=\{a,b,c,d\}$. The sum $b+c$ lies outside $A$, so belongs to $a+(A\setminus \{a\})$. It is neither $a+b$ nor $a+c$, and must therefore equal $a+d$. Thus $a+b+c+d=0$. The other three points have sum zero because the sum of all seven nonzero vectors is zero. They therefore form a line. In any two-colouring one colour has at least four points: if it contains a line we are done, and otherwise the other colour contains a line. This proves non-two-colourability.

Partition the host vertices of a hypergraph into sizes $a,b$ and take all triples meeting both parts. This bipartite three-uniform hypergraph has Property B and is consequently Fano-free. Its edge count isThe product $ab$ is maximized at balanced integer sizes. Writingwe have the exact lower bound $\mathrm{ex}(n,F)\ge b(n)$, and $b(n)=(3/4+o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$.

The structural step is Fano stability: a Fano-free hypergraph with density sufficiently close to $3/4$ has a bipartition with at most $\rho n^3$ internal triples, for any prescribed $\rho >0$. Its proof studies four hypergraph link graphs around a complete four-vertex three-uniform configuration. Colour a pair by the link vertices of a hypergraph containing it. Three perfect matchings in a graph on four other vertices of a hypergraph, with distinct colours corresponding to a triple of the configuration, would complete a Fano copy. Thus these rainbow patterns are forbidden. The near-extremal total link degree forces, after removing a small exceptional set, an almost balanced pattern with pair multiplicity two within the two classes and four between them. Internal triple density bounded away from zero produces many complete tripartite six-vertex templates; the nearly complete links then supply three paired neighbours and complete a Fano plane. Consequently the internal triple density tends to zero. These are the main ingredients of the stability argument: link degree counting supplies the approximate partition, and the forbidden completion templates eliminate positive internal density.

To see concretely why stability gives the exact bound, suppose $e(H)\ge b(n)$, and first obtain high minimum hypergraph vertex degree. Delete any vertex of degree at most $3m^2/8-2m$ when the current order is $m$. Directly from the formula for $b$, for large $m$,After deletions down to order $m$, the remaining hypergraph therefore has at least $b(m)+n-m$ edges. It cannot reach $m=\lceil n^{1/3}\rceil$, since this exceeds $\left(\genfrac{}{}{0ex}{}{m}{3}\right)$ for large $n$. The process stops at an order still tending to infinity, with minimum degree of a graph greater than $3m^2/8-2m$. If the high-minimum-degree case has at most $b(m)$ edges, any deletion gives a contradiction. Thus it suffices to treat that case; rename its order $n$.

Apply stability with a very small constant, for example $\rho =10^{-12}$, and choose a partition $A\bigsqcup B$ minimizing the number of internal hyperedges. Its part sizes are close to $n/2$, since its cross-part capacity is $|A||B|(n-2)/2$, and $e(H)\ge b(n)$ leaves at most $\rho n^3$ available compensation for any imbalance. In particular $||A|-n/2|,||B|-n/2|\le 2\sqrt{\rho }n$ for large $n$. Optimality also giveswith the analogous inequality for $x\in B$: otherwise moving $x$ would reduce the internal count.

Suppose some $x\in A$ has more than $n^2/100$ edges in its same-side link. Its opposite-side link then has at least as many. Each link has a matching in a graph of size at least $\lfloor n/300\rfloor$: the endpoints of a maximal matching in a graph cover every edge, so a matching in a graph of size $s$ bounds the link edge count by $2sn$. For each choice of one matching in a graph edge in $A$ and two matching in a graph edges in $B$, the six vertices of a hypergraph plus $x$ would form a Fano plane if all transversal triples through the three pairs were present. Specifically take the three triples through $x$ and the four even-parity transversal triples. Hence at least one of these cross-part triples is missing. The matchings in a graph are disjoint, so different choices give different missing triples. There are at leastFor large $n$ this exceeds $\rho n^3$, contradicting the edge count: the missing cross triples already outweigh every internal triple. Thus every same-side link has at most $n^2/100$ edges.

If an internal triple $xyz\subseteq A$ remains, high minimum degree of a graph gives, for each of its vertices of a hypergraph,The intersection of the three opposite-side links therefore has at least their total edge count minus $2\left(\genfrac{}{}{0ex}{}{|B|}{2}\right)$. Using $|B|\le (1/2+2\sqrt{\rho })n$, this exceeds $|B{|}^2/3$ for large $n$. By the quadratic Turan theorem bound, their intersection contains $K_4$. Its three perfect matchings in a graph, assigned to $x,y,z$, together with $xyz$ are the seven edges of a Fano plane. This is precisely Fano completion through three matchings, and gives a contradiction. The same argument excludes internal triples in $B$.

Thus the high-minimum-degree hypergraph is genuinely bipartite, not merely approximately so, and has at most $b(n)$ edges. The deletion argument proves the same bound for the original hypergraph. Combining with the balanced construction yieldsThis proof description keeps the essential roles distinct: non-two-colourability gives the lower construction, link-graph stability gives an approximate partition, and the minimum-degree/matching in a graph argument removes the last internal edges. The ceiling in the final term is confirmed by the PDF; the converted TeX incorrectly repeats the floor.

Write $\alpha =1-1/r$. The Erdős-Stone theorem states that, for a fixed graph $F$ with chromatic number $\chi (F)=r+1\ge 2$,Here $\mathrm{ex}$ is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write $K_a(b)$ for the balanced complete multipartite blow-up with $a$ classes of $b$ vertices each. All asymptotic errors below concern $n\to \infty$ with the forbidden graphs fixed.

The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For $r=1$, the edgeless spanning subgraph suffices. Suppose $r\ge 2$.

First repeatedly remove a vertex whose degree of a vertex is less than $(\alpha -{\epsilon }_n)$ times the current order, where ${\epsilon }_n\to 0$ sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every $K_{r+1}(t)$-free subgraph $J$ of order at most $n$,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to $n^2$. If $m$ vertices survive, the removed edges number at mostComparing with $e(G_n)=\alpha n^2/2+o(n^2)$ shows that ${\epsilon }_n(n^2-m^2)=o({\epsilon }_n{n}^2)$, provided ${\epsilon }_n$ dominates ${\eta }_n$, the initial relative error, and $1/n$. Consequently $m=n-o(n)$. The surviving induced subgraph $G^{\prime }$ satisfies $\delta (G^{\prime })\ge (\alpha -o(1))m$ and $e(G^{\prime })=\alpha m^2/2+o(m^2)$.

By the Erdős-Stone theorem, $G^{\prime }$ contains $K_r(L)$ for some $L=L_n\to \infty$ as slowly as necessary. This follows because $\alpha$ exceeds the extremal number density for each fixed $K_r(L)$ by the positive gap $1/(r(r-1))$. Choose $L$ so slowly that $rL=o(m)$ and ${\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$, and denote its root classes by $A_1,\dots ,A_r$.

An outside vertex having at least $t$ neighbours of a vertex in every $A_i$ determines one choice of a $t$-subset in each $A_i$. At most $t-1$ outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form $K_{r+1}(t)$. Thus at most $(t-1){\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$ outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class $C_i$ for which it has fewer than $t$ neighbours of a vertex in $A_i$.

Write $\delta (G^{\prime })\ge (\alpha -{\gamma }_n)m$, with ${\gamma }_n\to 0$. Counting missing incidences with $A_i$ givesSince ${\sum }_i|C_i|=m-o(m)$, it follows that $|C_i|=m/r+o(m)$ for every $i$. The total missing incidences from all root vertices to assigned vertices are at most $(1+r{\gamma }_n)Lm$. At least $(L-t+1)(m-o(m))$ of them are incidences with a vertex's own assigned root class. Hence only $o(Lm)$ missing incidences go to other root classes.

Choose ${\rho }_n\to 0$ slowly and discard the $o(m)$ assigned vertices with more than ${\rho }_{n}L$ missing incidences to other root classes. Each remaining vertex of $C_i$ is adjacent to all but at most ${\rho }_{n}L$ vertices of every $A_j$, $j\ne i$. If its class contained a complete bipartite graph $K_{t,t}$, the $2t$ vertices of this copy would have at least $L-2t{\rho }_{n}L\ge t$ common neighbours of a vertex in each other root class. These sets extend the copy to $K_{r+1}(t)$, a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is $o(m^2)$.

The surviving graph still has $\alpha m^2/2+o(m^2)$ edges, whereas the total possible cross-class edges, with these balanced classes, is $\alpha m^2/2+o(m^2)$. Thus only $o(m^2)$ cross-class edges are missing. Discard the $o(m)$ vertices missing more than ${\sigma }_{n}m$ cross-class edges, with ${\sigma }_n\to 0$ slowly, and delete all internal edges. The resulting $r$-partite subgraph $H$ has classes $H_i$ of size $n/r+o(n)$ andFor the lower bound, every surviving vertex misses only $o(n)$ vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.

Minimum degree in an extremal graph. Fix $F$ with $\chi (F)=r+1$. Choose $t$ large enough that $F$ embeds in $K_{r+1}(t)$. An extremal $F$-free graph $G$ is therefore $K_{r+1}(t)$-free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For $r\ge 2$ take $H$ as above.

For any vertex $v$, remove $v$ and introduce a new vertex $v^{\ast }$ whose vertex neighbourhood consists precisely of the vertices in $H_2\cup \cdots \cup H_r$ other than $v$. The new degree of a vertex is $\alpha n-o(n)$. This new graph remains $F$-free. Indeed, a new copy of $F$ must use $v^{\ast }$, and all its neighbours of a vertex in that copy lie in the other classes of $H$. There are only boundedly many of them. Each misses only $o(n)$ vertices in $H_1$, so an unused vertex $w\in H_1$ is adjacent to all of them. Replacing $v^{\ast }$ by $w$ would give $F$ in $G-v$, which is impossible.

Extremality now forces $d_G(v)\ge \alpha n-o(n)$, uniformly in $v$. The upper bound for the minimum degree of a graph follows from $\delta (G)\le 2e(G)/n$. For $r=1$, $e(G)=o(n^2)$ already gives $0\le \delta (G)=o(n)$. ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.

The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turán graph contains no $K_{r+1}$, so every such clique in $J_s(n)$ uses a vertex of $K_{s-1}$. Therefore $J_s(n)$ contains no $s$ vertex-disjoint such cliques, and the extremal number is at least $b_s(n)$.

Induct on $s$, with $s=1$ supplied by the Turan theorem, including its equality characterization. Let $s\ge 2$ and let $G$ be extremal for $s{K}_{r+1}$. The preceding results give $\delta (G)\ge \alpha n-o(n)$ and the $r$-partite subgraph $H$. Keep its classes $H_i$ fixed and assign each of the remaining $o(n)$ vertices to a class in which it has fewest neighbours of a vertex in $H$. Write the resulting classes as $C_i$; all have size $n/r+o(n)$. Choose a positive ${\tau }_n\to 0$ so slowly that ${\tau }_{n}n$ dominates the outside count, every cross-class error in $H$, and every error in the minimum degree of a graph bound.

Suppose some vertex $x\in C_i$ has at least ${\tau }_{n}n$ internal neighbours of a vertex. If $x\notin H$, the assignment rule shows that $x$ has at least ${\tau }_{n}n-o(n)$ neighbours of a vertex in every $H_j$. If $x\in H_i$, it has this many in $H_i$ and $n/r-o(n)$ in the other $H_j$. If $G-x$ contained $s-1$ disjoint $K_{r+1}$, we could choose one vertex in each $N(x)\cap H_j$, successively avoiding those copies and the $o(n)$ missing cross-neighbours of the already chosen vertices. This produces a further $K_{r+1}$ through $x$. For $r=1$, this just chooses an unused neighbour of $x$. Hence $G-x$ is $(s-1)K_{r+1}$-free, and induction givesSince the candidate attains $b_s(n)$, equality holds throughout: $x$ is a universal vertex and $G-x$ is the inductively unique extremal graph. Thus $G$ is isomorphic to $J_s(n)$.

It remains to show that this case must occur. Otherwise all internal vertex degrees are less than ${\tau }_{n}n=o(n)$. Together with the lower bound on $\delta (G)$ and $|C_i|=n/r+o(n)$, this implies that every vertex misses only $o(n)$ vertices outside its own class. If some $C_i$ contains a matching in a graph of $s$ edges, extend its edges one by one to $K_{r+1}$, choosing one vertex from each other class. At every step only $o(n)$ cross-neighbours and boundedly many used vertices are excluded. This gives $s$ disjoint forbidden cliques, a contradiction.

A maximal matching in each class therefore has at most $s-1$ edges, and its at most $2(s-1)$ endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all $o(n)$, so the total internal edge count is $o(n)$. The cross-class edge count is at most $e(T_r(n))$, whenceBut the balanced part sizes of the Turán graph givecontradicting extremality for $s\ge 2$. This argument also works for $r=1$. Consequently, for all sufficiently large $n$,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.

Use natural logarithms. A $K_t$ graph minor is represented by $t$ disjoint nonempty branch sets of a graph minor, each inducing a connected graph, with an edge between every pair. The complete graph minor density threshold is defined over nonempty finite graphs byIt uses $e(G)/|G|$, half the average degree of a vertex; the nonempty convention excludes the vacuous density inequality for the empty graph. The PDF has the intended definition with a universal implication over $G$; the TeX transcription corrupts that definition.

Probabilistic lower bound. Put $N=\lfloor t\sqrt{\log t}/4\rfloor$ and take the binomial random graph $G(N,1/2)$. Its edge count has mean $N(N-1)/4$. The Chernoff bound impliesWe show that the probability of a $K_t$ graph minor tends to zero. Ignore connectedness, which only enlarges the set of possible models, and assign each of the $N$ vertices one of $t$ branch labels or an unused label. There are at most $(t+1{)}^N$ assignments.

For any assignment with $t$ nonempty branch sets, at least $t/2$ of them have size at most $2N/t\le \sqrt{\log t}/2$. Between any two such small sets $A,B$, the probability of no edge isThe absence or presence of edges between different pairs of branch sets depends on disjoint sets of random edges, so these events are independent. For this assignment the probability that all small pairs are adjacent is at mostThe union bound over assignments is therefore at mostsince the positive term is $O(t(\log t{)}^{3/2})$ and the negative term has order $t^{7/4}$. There is consequently a graph with no $K_t$ graph minor and with $e(G)/N\ge N/8$. Any constant having the universal forcing property must exceed this ratio. Since $N/8\ge t\sqrt{\log t}/64$ for large $t$,

The auxiliary density lemma contains a typo. Both the original PDF and the TeX print $e(G)\le 11k|G|$ in the hint. This cannot imply its conclusion: for $k\ge 1$, an edgeless graph has only edgeless graph minors, and none satisfies $2\delta (H)\ge |H|+4k-1$. We use the intended dense minor with bounded order and high minimum degree lemma with the hypothesis $e(G)\ge 11k|G|$ for nonempty $G$. The upper-bound argument below depends on that corrected supplied lemma; the literal printed hint is false.

Probabilistic upper bound and the constant seven. Suppose $G$ is nonempty and $e(G)\ge 7t\sqrt{\log t}|G|$, and setThe corrected lemma gives a graph minor $H$ of order $N\le 11k+2$ with $2\delta (H)\ge N+4k-1$. Since $\delta (H)\le N-1$, we also have $N\ge 4k+1$. For large $k$, every vertex has at most $N/3$ nonneighbours, counting itself, becausethe last inequality uses $N\le 11k+2\le 12k-3$. Moreover any two distinct vertices have at leastcommon neighbours.

Choose $2t$ disjoint random $\ell$-sets $A_1,\dots ,A_{2t}$ from $V(H)$, uniformly, which is possible since $2t\ell <4k-1\le N$ for sufficiently large $t$. For a set $A$, let $U(A)$ be the set of vertices having no neighbour in $A$. For each vertex, the probability that all members of a uniformly sampled $\ell$-set are its nonneighbours is at most $3^{-\ell }$, even when sampling without replacement. By linearity of expected value,Call $A$ good if $|U(A)|\le N{3}^{-19\ell /20}$. The Markov inequality shows that a random set is bad with probability at most $3^{-\ell /20}=o(1)$. Thus the expected number of bad sets among our $2t$ samples is $o(t)$.

Conditional on a fixed good $A_i$, the marginal distribution of $A_j$ is uniform among $\ell$-sets outside $A_i$. For there to be no edge between them, all its members must lie in $U(A_i)$. HenceHere $(N/(N-\ell ){)}^{\ell }=\exp (O({\ell }^2/N))=1+o(1)$. Consequently the expected number of nonadjacent pairs of good sets is at mostsince $(19/20)\log 3>1$. Applying the Markov inequality to both counts shows that there exists a choice with fewer than $t$ bad sets and at most $t$ nonadjacent pairs of good sets. Select $t$ of the good sets; they still have at most $t$ missing adjacencies.

Make each selected set connected by fixing one of its vertices as a root and, for each of its other members, adding one unused common neighbour of that member and the root. This uses at most $t(\ell -1)$ additional vertices. Then for each pair with no original edge, choose one vertex in each set and add an unused common neighbour to one of the sets. The added vertex is joined to that set and to the other set, so it preserves connectedness and repairs their adjacency. At most $t$ such repairs are required.

Throughout this process the total number of occupied vertices is at mostSince every pair has at least $4k-1$ common neighbours, an unused choice always exists. The final sets are disjoint connected branch sets of a graph minor with every pair adjacent. They represent $K_t$ in $H$, and hence in $G$, by transitivity of graph minors. This random branch-set construction of a complete graph minor proves

The sharp linear threshold for a four-vertex complete minor. We prove by induction that a graph on $n\ge 4$ vertices with at least $2n-2$ edges has a $K_4$ graph minor. The case $n=4$ is $K_4$ itself. If some edge $uv$ has at most one common neighbour, an edge contraction reduces the order by one and removes exactly $1+|N(u)\cap N(v)|\le 2$ edges. The contracted graph has at least $2(n-1)-2$ edges, so induction applies.

Otherwise every edge is in at least two triangles in a graph. Choose a vertex $v$ incident with an edge. Each vertex $u\in N(v)$ has at least two neighbours of a vertex in $N(v)$, since these are the common neighbours of $u,v$. Thus $G[N(v)]$ has minimum degree of a graph at least two. A longest path in this finite graph has an endpoint adjacent to an earlier nonconsecutive path vertex, and hence contains a cycle in a graph. Together with $v$, this cycle in a graph gives a wheel graph as a subgraph. Divide its rim into three consecutive nonempty connected arcs; these arcs and $\{v\}$ form four pairwise adjacent branch sets of a graph minor. Therefore

With $2n-3$ edges the answer is no. Take the join of graphs of $K_2$ and an independent set of $n-2$ vertices. It has $1+2(n-2)=2n-3$ edges. Among four disjoint putative branch sets of a graph minor, at most two can contain the two vertices of $K_2$. Any connected branch set avoiding them is a singleton in the independent set. At least two such singleton sets would therefore have no edge between them. This excludes a $K_4$ graph minor for every $n\ge 4$ and proves sharpness.

The graph Ramsey number $R(H)$ is the least $N$ such that every red-blue colouring of the edges of $K_N$ contains a monochromatic copy of $H$.

The minimum-degree Ramsey lower bound states that a graph of minimum degree $d$ admits an $H$-free colouring on every integer $N<2^{d/2}$. Its probabilistic proof colours edges independently and applies the local lemma to the events that a labelled copy of $H$ is monochromatic. Sincethe exponential cost $2^{1-e(H)}$ of a monochromatic copy dominates the number of compatible copies through every fixed edge. Hence such a colouring exists, and therefore

For every nontrivial graph, $\kappa (G)\le \lambda (G)\le \delta (G)$.

These compare two numerical invariants of connectivity with the minimum degree of a graph.