Skip to content

Erdős Problem #1079

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: solved (not automatically the live result).
Subject areas: graph theory, turan number.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Turán's theorem gives the maximum number of edges in a graph without a complete graph of prescribed order. Erdős Problem #1079 asks whether enough edges also force a dense neighborhood.

Fix \(r\ge4\). When a graph \(G\) has at least \(\mathrm{ex}(n,K_r)\) edges, then either it is the extremal Turán graph \(T_{r-1}(n)\), or there is a vertex \(v\) of degree \(d\) proportional to \(n\) whose neighbors span more edges than a \(K_{r-1}\)‑free graph could contain:

\[ e(G[N(v)])\ge\mathrm{ex}(d,K_{r-1})+1. \]

The extremal exception is essential.

A small example

For \(r=4\), take \(G=K_4\). It has six edges, while \(\mathrm{ex}(4,K_4)=5\). Every vertex has three neighbors, which themselves form \(K_3\) with three edges. But \(\mathrm{ex}(3,K_3)=2\). Thus there is exactly one extra neighborhood edge.

By contrast, the balanced tripartite \(T_3(4)\) has five edges and is the allowed exception. These are elementary instances, not the general theorem.

What is known

Bollobás and Thomason proved the conjecture in Dense neighbourhoods and Turán's theorem, Journal of Combinatorial Theory, Series B 31 (1981), 111–114. Their own public abstract confirms the high-degree neighborhood conclusion and the exact Turán exception. Bondy (1983) subsequently showed that above the strict Turán edge threshold a maximum-degree vertex can be chosen.

Notation is easy to confuse. The authors write \(t_s(n)\) for the \(s\)‑partite Turán edge count, so \(t_{r-1}(n)=\mathrm{ex}(n,K_r)\).

GCL's current state

Authenticated source audit #2350 compared the solved catalogue status to the authors' published abstract and independently checked the four-vertex example. The full 1981 and 1983 proofs have not undergone independent source-fidelity review.

What remains

Review the actual theorem pages, indexing, admissible \(r\), linear degree condition, equality exception and Bondy's stronger conclusion. The published theorem must be credited externally, not treated as a new GCL discovery.

Sources and claim boundaries

Erdős Problem #1079; Bollobás–Thomason (1981), publisher-record abstract, DOI 10.1016/S0095-8956(81)80016-0; Bondy (1983), source proof pending; GCL return #2350. This remains an unaccepted draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2350 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction