Skip to content

Erdős Problem #133

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory.

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.

The question in plain language

A graph has diameter two when any two distinct vertices are connected by a path of length at most two, and at least one pair is not adjacent. Let \(f(n)\) be the smallest possible maximum vertex degree among all triangle-free graphs with \(n\) vertices and diameter two.

Erdős and Pach asked how \(f(n)\) grows, and in particular whether

\[ \frac{f(n)}{\sqrt n}\longrightarrow\infty. \]

That second conjecture predicts the required maximum degree is much larger than the square-root scale, not merely a positive constant times \(\sqrt n\).

A small example

If a graph has maximum degree \(d\) and diameter two, choose any vertex. It reaches at most \(d\) neighbours in one step and at most \(d(d-1)\) new vertices through those neighbours. Thus

\[ n\le1+d+d(d-1)=d^2+1. \]

Therefore every diameter-two graph has \(d\ge\sqrt{n-1}\), whether or not triangles are forbidden. A five-cycle is triangle-free, has diameter two, and has maximum degree two; its \(n=5\) satisfies the elementary lower bound exactly.

What is known

The prediction \(f(n)/\sqrt n\to\infty\) is DISPROVED; the sharp leading constant remains OPEN. Hanson and Seyffarth (1984) constructed Cayley graphs giving

\[ f(n)\le(\sqrt2+o(1))\sqrt n. \]

Füredi and Seress, Maximal triangle-free graphs with restrictions on the degrees, Journal of Graph Theory 18 (1994), 11–24, improved the upper constant to

\[ f(n)\le\left(\frac2{\sqrt3}+o(1)\right)\sqrt n. \]

Together with the elementary lower bound, the order is \(\Theta(\sqrt n)\), but the precise asymptotic constant is not determined. The maintained Erdős #133 attributes a conjectural constant one to Alon; it is not a proved limit.

A separate simpler construction due to Alon, documented on the maintained site, gives \(f(n)\ll\sqrt{n\log n}\) by starting with a high-chromatic triangle-free example and adding edges without creating triangles until diameter two. This is weaker asymptotically than the cited constant-times-square-root construction.

GCL's current state

The pinned catalogue and maintained page classify the proposed divergence as DISPROVED. The original issue is #1402. The exact degree-two neighbourhood inequality is independently verified. The full 1984 and 1994 Cayley/construction proofs are cited from the maintained source and primary publication trail but were not independently rebuilt.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded successor enumerates triangle-free graphs on up to seven vertices, checks graph diameter and maximum degree, and compares the smallest maximum degree with \(\lceil\sqrt{n-1}\rceil\). Acceptance: \(C_5\) is recognized as triangle-free, diameter two, and degree two; disconnected graphs are rejected as having infinite diameter. Stop at finite consistency checks, not a new leading-constant theorem.

Sources and claim boundaries

No proof of the proposed constant one or independent proof of all finite-group constructions is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1402 — 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