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
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
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ü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
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
- Füredi–Seress, J. Graph Theory 18 (1994), 11–24, primary bibliographic source.
- Maintained Erdős #133, historical constructions and open exact constant.
- Original GCL issue #1402.
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.