Computing cycle-length sets for graphs on 11 vertices

Counting cycle-length sets

A graph consists of vertices joined by edges. We consider simple undirected graphs, which have no edge directions, self-loops, or duplicate edges.

A simple cycle follows edges back to its starting vertex without visiting any other vertex twice. Its length is the number of edges it uses. The cycle-length set C(G) contains every simple-cycle length in a graph G. A cycle can have extra edges between its vertices; it need not be induced.

A square with one diagonal has two triangles and a cycle of length four. Its cycle-length set is {3, 4}. Each length appears once in the set, regardless of how many cycles have that length.

The number f(n) counts the different cycle-length sets that graphs on exactly n vertices can have. Graphs may be disconnected. A graph with no cycles has the empty set, and adding isolated vertices leaves its cycle-length set unchanged.

The candidate count: f(11) = 247

Our computation supports the candidate value f(11) = 247. Two classifiers each processed 1,018,997,864 non-isomorphic graphs on 11 vertices. Both found the same 247 sets. A separate verifier checked one saved example graph, called a witness, for each set.

The lower bound f(11) ≥ 247 means that at least 247 sets occur. This bound was already public: Patrick White’s July 2026 report supplied 247 witnesses. Our separate witness checks also establish this lower bound.

The upper bound f(11) ≤ 247 means that at most 247 different sets occur. Our computation supports this bound if nauty geng 2.9.3 generated one representative of every 11-vertex graph isomorphism class and both classifiers computed the correct cycle-length set for every graph. Under those conditions, the matching bounds give f(11) = 247.

How the graphs were classified

Relabeling vertices leaves a graph’s cycle-length set unchanged. Graphs that differ only by relabeling belong to the same isomorphism class, so checking one graph from each class is sufficient.

Both scans used geng 2.9.3, the graph generator from nauty and Traces. Each classifier received a separately generated stream. Each generator run and classifier reported 1,018,997,864 records. The deterministic scans used no random seed and did not save the billion-record graph streams.

Each classifier stores a cycle-length set as a nine-bit number, called a mask. Each bit records whether one length from 3 through 11 occurs. The first classifier searches for one length at a time. It extends paths from their least-numbered vertex and checks for an edge back to that vertex.

The second classifier collects all cycle lengths in one traversal. It tracks the current vertex and the set of visited vertices, and saves these states to avoid repeating work. It also has a separate decoder for graph6, the format used to store each graph.

What the checks establish

The two full scans produced byte-for-byte identical 247-mask result files. The classifiers also agreed on each graph through 10 vertices and reproduced the known count f(10) = 133. For 11 vertices, the comparison checked the final collections of sets, not agreement on each individual graph.

The separate Python verifier recomputes each witness’s entire cycle-length set. It uses its own graph6 decoder, selects subsets of vertices, and checks cyclic orderings of those vertices. It confirms that the result matches the saved mask and length list, and that all 247 masks differ. These checks establish the lower bound without relying on either classifier.

Package checks compare graph counts and verify SHA-256 checksums to detect changes to the saved files. Matching counts and unchanged files support the run record; they do not establish that the generator covered every graph.

Prior work and the broader problem

Alvin Dunås computed the exact values through f(10) = 133. His June 2026 Uppsala University report is titled The number of sets of cycle lengths for graphs on n vertices. Patrick White’s report independently reproduced that table and established f(11) ≥ 247.

The September 3, 2026 prior-work search found no indexed claim of an exact value for f(11). That search cannot exclude private, unindexed, or later work. Repeat the literature search before claiming that the exact count is new.

Erdős Problem #84 concerns how f(n) grows as n increases. Counting the sets for 11 vertices does not resolve the remaining question about that growth.

Remaining limits and review

The upper bound still depends on complete graph generation and correct classification. Both classifiers use the same generator, so their agreement cannot rule out a shared omission in the generated graphs.

The archive records graph counts and checksums, but it does not formally certify that the generator covered every graph class. Qualified expert review of the upper-bound argument remains incomplete.

Manuscript submission

Zachary Roth submitted the manuscript to The Electronic Journal of Combinatorics on September 4, 2026. Its title is The number of cycle sets of graphs on 11 vertices. Submission does not establish acceptance or completed peer review. As of September 14, 2026, we had not checked the journal’s current editorial status.

AI contributions

OpenAI Codex provided substantial assistance with source searches, program development, verification, documentation, and manuscript preparation. Zachary Roth is the manuscript’s author; Codex is not an author. AI assistance does not replace mathematical review.

Sources and reproduction

The public code and data archive on Zenodo (version 1.0.0, DOI 10.5281/zenodo.22308104) was accessible on September 14, 2026. Its ZIP contains the classifiers, witness verifier, saved witnesses, tests, raw logs, checksums, and reproduction guide.

To reproduce the computation, you need Python 3.9 or later, a C++17 compiler, a POSIX environment such as macOS or Linux, and at least 1 GB of available memory. The original 11-vertex scan took about 55 minutes on an Apple M4 Pro. Other systems may take longer.

To audit the preserved package first, run python3 review/erdos84/verify_package.py --quick. Omit --quick to add the approximately five-minute witness verification.

1. Download and extract the ZIP from the Zenodo archive.
2. Follow the commands in review/erdos84/REPRODUCE.md to build the generator and both classifiers.
3. Run the 10-vertex check. The expected count is f(10) = 133.
4. Run both 11-vertex scans and compare their results. Each should report 1,018,997,864 graphs and the same 247 cycle-length sets.
5. Run the separate verifier on each scan’s saved witnesses. Each verification should finish without errors.

• Erdős Problem #84: statement and history.
• Alvin Dunås’s Uppsala report (the institutional site may show an anti-bot check).
• Patrick White’s July 2026 report and lower-bound certificate.