Skip to main content

Erdős Problem #84: Cycle-length sets

How many different sets of cycle lengths can graphs have?

A triangle, square, and pentagon illustrate different cycle lengths.
These three separate graphs have the cycle-length set {3, 4, 5}.

The problem

A graph’s cycle-length set records the length of every simple cycle it contains. The function f(n) counts how many such sets occur among graphs on n vertices. Erdős Problem #84 asks how f(n) grows.

Read the problem statement and history.

Research note

Status

An exhaustive computation found 247 cycle-length sets on 11 vertices, matching the public examples. The result depends on complete graph generation and correct classification. It awaits expert review and does not resolve the broader problem.

Submitted to The Electronic Journal of Combinatorics on September 4, 2026; not yet accepted or peer reviewed.