OctoInformBeta

OpenAI preprint, September 2026 · Section 6. From triangle mass to independent sets

Passing to average degree in the proof of Theorem 1.1: The threshold is twice a positive average degree, and induced subgraphs have no larger independence number

Half the vertices have controlled degree.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let G=(V,E)G=(V,E) be a finite simple graph, and write n=|V|n=|V|. The degree deg⁡G(v)\deg_G(v) of a vertex vv is its number of neighbours in GG. For n>0n>0, the average degree d(G)d(G) of GG is the real number given in (1): d(G)=2|E||V|.d(G)=\frac{2|E|}{|V|}.(1) For a positive real number dd, the degree cutoff AdA_d is the subset of VV defined in (2): Ad={v∈V:deg⁡G(v)≤2d}.A_d=\{v\in V:\deg_G(v)\le 2d\}.(2)

For a subset A⊆VA\subseteq V, the induced subgraph G[A]G[A] has vertex set AA and the edges of GG with both endpoints in AA. The independence number α(G)\alpha(G) is the largest cardinality of a subset of VV containing no adjacent pair.

The Claim

Theorem 1. Let G=(V,E)G=(V,E) be a finite simple graph with n=|V|n=|V|. If d>0d>0 and ∑v∈Vdeg⁡G(v)=nd\sum_{v\in V}\deg_G(v)=nd, then the degree cutoff in (2) satisfies n2≤|Ad|.\frac{n}{2}\le |A_d|.(3)✦ For every subset A⊆VA\subseteq V, α(G[A])≤α(G).\alpha(G[A])\le\alpha(G).(4)✦

In the paper, with KrK_r denoting the complete graph on rr vertices, the result reads: for a KrK_r-free graph with nn vertices and average degree d=d(G)≥2d=d(G)\ge2, retaining vertices of original degree at most 2d2d gives an induced KrK_r-free graph on at least n/2n/2 vertices with maximum degree at most 2d2d, and Proposition 6.1 yields α(G)≥nlog⁡d/(16Drd)\alpha(G)\ge n\log d/(16D_r d), where DrD_r is the constant in that proposition, so one may take cr=1/(16Dr)c_r=1/(16D_r).

What Is Checked

The bound (3) is stated for finite simple graphs and a positive real dd satisfying the degree sum identity, and (4) is stated for every vertex subset of a finite simple graph.