Skip to content

Erdős Problem #84

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

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

For a finite graph \(G\) on \(n\) vertices, write \(L(G)\) for the set of integers \(\ell\) for which \(G\) contains a simple cycle with exactly \(\ell\) edges. A graph with triangles and five-cycles but no four-cycles has cycle set \(\{3,5\}\).

Erdős and Faudree ask how many different cycle sets can arise among all simple graphs on \(n\) labelled vertices. Denote this number by \(f(n)\). Erdős #84 has two distinct asymptotic questions:

\[ f(n)=o(2^n),\qquad \frac{f(n)}{2^{n/2}}\longrightarrow\infty. \]

They are not equivalent. Two graphs are counted only once if their cycle-length sets agree, even if their edge sets are completely different.

A small example

A forest has no cycles and thus has cycle set \(\varnothing\). A triangle plus isolated vertices has set \(\{3\}\); an induced square plus isolated vertices has set \(\{4\}\). Adding disjoint triangles and squares gives set \(\{3,4\}\), because each connected component contributes its own cycle lengths. This construction shows why counting graphs directly is misleading: many graphs give the same cycle set.

The obvious upper bound is \(2^{n-2}\) because a cycle set is a subset of \(\{3,\ldots,n\}\). Improving that trivial estimate is a theorem about dependencies between cycle lengths, not a matter of listing all possible subsets.

What is known

The first conjecture is PROVED. J. Verstraëte proved that there are at most \(2^{n-n^{1/10}}\) different cycle sets, which is \(o(2^n)\). Rajko Nenadov strengthened this in Improved bound on the number of cycle sets, published in Combinatorial Theory 6 (2026), article 17, to

\[ f(n)\le 2^{\,n-n^{1/2-o(1)}}. \]

The primary abstract explicitly identifies container arguments for cycle sets of Hamiltonian graphs as the new mechanism.

The second question, requiring growth faster than \(2^{n/2}\) by an unbounded factor, remains OPEN. Erdős and Faudree had established a strict \(2^{n/2}\) scale lower bound, but that does not supply an unbounded multiplicative factor. The maintained page therefore classifies the overall entry as open despite the first conjecture's resolution.

GCL's current state

The GCL original assignment is #1353. The primary Nenadov preprint abstract and the 2026 published metadata were inspected. The pinned and maintained overall statuses are OPEN, and no protected Formal Conjectures statement exists in the admitted snapshot. A full independent proof of the container bounds was not attempted.

An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.

What remains

A bounded exact test is to enumerate all labelled graphs on five vertices, calculate each graph's cycle-length set using a deterministic simple-cycle search, and deduplicate the resulting sets. Acceptance: every reported cycle has distinct internal vertices and exactly the recorded length, and two isomorphic or nonisomorphic graphs with identical length sets contribute only one count. Stop at five vertices. This is a source-semantic fixture, not an extrapolation to the unresolved asymptotic lower bound.

Sources and claim boundaries

Only the first conjunct is known; no solution to the second question, new enumerative theorem, or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1353 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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