Erdős problem #585 — live audit and exact small cases

Date: 2026-07-28 (UTC)

Claim labels used below:

• [a] elementary-rigorous — a complete finite argument is given.
• [b] rigorous-modulo-named-theorem — the claim is quoted from a named, verified primary source.
• [c] plausible/structural-unverified — a diagnosis or proposed route, not a theorem.
• [d] computational-only — an exhaustive finite computation, with its trust boundary stated.

0. Mandatory live-page check

I fetched the live Erdős Problems page #585 through the Bright Data browser route on 2026-07-28. Direct page metadata was not inferred from the stale YAML.

The page status was OPEN. It displayed:

• 0 comments on this problem;
• 0 claimed proofs for this problem;
• Interested in collaborating: None;
• Currently working on this problem: None;
• all other work/difficulty/formalisation markers as None (apart from a like by Alfaiz).

Thus the stop condition did not apply.

The live-page statement, verbatim, is:

What is the maximum number of edges that a graph on \(n\) vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?

The live page lists exactly these substantive known results:

1. Pyber, Rödl, and Szemerédi constructed such graphs with

\(\gg n\log\log n\) edges.

1. Chakraborti, Janzer, Methuku, and Montgomery proved an upper bound

\(n(\log n)^{O(1)}\). More precisely, there is an absolute \(C>0\) such that, for every \(k\geq 2\), some \(c_k\) guarantees \(k\) pairwise edge-disjoint cycles with the same vertex set once the graph has at least \(c_kn(\log n)^C\) edges.

No statement below treats the tags or stale tracker metadata as mathematical input.

1. Primary-source literature audit

• Erdős's original 1976 paper, Problem 29 defines the threshold \(f_2(n)\) for two edge-disjoint circuits having the same vertex set and says that he did not know its order. The PDF and problem number were checked directly. [b]

• Pyber, Rödl, and Szemerédi's paper really exists as

Dense Graphs without 3-Regular Subgraphs, J. Combin. Theory Ser. B 63 (1995), 41–54, DOI 10.1006/jctb.1995.1004. (The live-page bibliography says “Dense subgraphs”; the publisher title is “Dense Graphs”.) Its abstract states the \(cn\log\log n\) construction. The later paper below explicitly records that the construction supplies graphs with no \(4\)-regular subgraph and hence the lower bound relevant here. [b]

• Chakraborti, Janzer, Methuku, and Montgomery,

Edge-disjoint cycles with the same vertex set, arXiv:2404.07190, Theorem 2, proves: for some absolute integer \(t\), and for every \(k\geq2\), every sufficiently dense \(n\)-vertex graph with at least \(c(k)n(\log n)^t\) edges has \(k\) such cycles. The paper was published in Advances in Mathematics 469 (2025), article 110228, DOI 10.1016/j.aim.2025.110228. [b]

• Janzer, Steiner, and Sudakov,

Chromatic number and regular subgraphs, arXiv:2410.02437, is genuinely related: it constructs graphs of growing fractional chromatic number with no \(4\)-regular subgraph. It addresses the chromatic-number analogue, not an improvement of the \(n(\log n)^{O(1)}\) edge upper bound for this problem. [b]

Targeted searches for the exact problem phrase, the title/arXiv citations, and 2025–2026 follow-up work found the 2025 journal publication and the related chromatic paper above, but no primary source improving the displayed \(\Omega(n\log\log n)\) versus \(n(\log n)^{O(1)}\) gap. This is a reported search miss, not a claim that no such paper exists.

2. Exact structural reduction

Let \(F(n)\) denote the requested maximum. Throughout, “graph” has its standard meaning in the cited extremal-graph sources: a finite simple undirected graph.

If \(C_1,C_2\) are edge-disjoint cycles with common vertex set \(S\), then each vertex of \(S\) has two incident edges in each cycle. Hence \(C_1\cup C_2\) is a \(4\)-regular spanning subgraph on \(S\), with an edge decomposition into two Hamilton cycles. Conversely, every such decomposable \(4\)-regular subgraph is a forbidden pair. [a]

It is important that “decomposable into two Hamilton cycles” not be dropped: an arbitrary \(4\)-regular subgraph only has a decomposition into 2-factors in general, and those factors may each have several cycle components.

Two small witnesses drive much of the computation:

• \(K_5\) is the disjoint union of the cycles

\[ (0,1,2,3,4),\qquad (0,2,4,1,3). \]

• If \(M=\{03,14,25\}\), then \(K_6-M\) is the disjoint union of

\[ (0,1,2,3,5,4),\qquad (0,2,4,3,1,5). \]

Both identities are checked edge by edge by the companion script. [a]

Equivalently, writing \(H=\overline G\):

• an independent 5-set in \(H\) exposes a \(K_5\) in \(G\);
• a 6-set \(S\) for which \(H[S]\) is a matching exposes a

\(K_6-M\) in \(G[S]\), since that matching extends to a perfect matching.

This converts the upper search into a monotone missing-edge covering problem.

A general elementary lower bound is \(F(n)\geq 3n-6\) for \(n\geq3\): start with \(K_3\) and add each later vertex with exactly three neighbours among earlier vertices. This gives a 3-degenerate graph with \(3n-6\) edges, which cannot contain a \(4\)-regular subgraph. [a] The small certificates below improve this from \(n=7\) onward.

3. New exact small-case table

The computation gives

| \(n\) | \(\binom n2\) | minimum missing edges | \(F(n)\) | |---:|---:|---:|---:| | 1 | 0 | 0 | 0 | | 2 | 1 | 0 | 1 | | 3 | 3 | 0 | 3 | | 4 | 6 | 0 | 6 | | 5 | 10 | 1 | 9 | | 6 | 15 | 3 | 12 | | 7 | 21 | 5 | 16 | | 8 | 28 | 9 | 19 | | 9 | 36 | 13 | 23 | | 10 | 45 | 18 | 27 |

Thus

The entries through \(n=6\) have short elementary proofs. For \(n=5\), the only possible common set has five vertices, and two cycles require all ten edges of \(K_5\). For \(n=6\), let \(H=\overline G\). If a 13-edge graph has two missing edges which meet, deleting their common endpoint leaves a \(K_5\); if they are disjoint, extend them to a perfect matching and use \(K_6-M\). Monotonicity then covers graphs with 14 or 15 edges. Conversely, \(K_6-K_3\) has 12 edges, no \(K_5\), and its three missing triangle edges cannot lie in a perfect matching. [a]

There is also a clean elementary lower certificate at \(n=7\): \(G_7=K_7-C_5\). It has no \(K_5\), because \(\alpha(C_5+2K_1)=4\). Deleting any one vertex from the complement leaves adjacent missing edges, so no 6-set contains \(K_6-M\). On all seven vertices, the five vertices lying on the missing \(C_5\) have degree exactly four in \(G_7\); a spanning 4-regular subgraph would therefore use every edge from them to each of the other two vertices, forcing degree five at those two vertices. [a]

The \(n=8\) lower certificate is obtained from this \(G_7\) by adjoining a vertex of degree three, which cannot participate in a 4-regular forbidden union. [a] The upper bounds for \(7\leq n\leq10\), and the \(n=9,10\) lower certificates, are computational-only [d] as detailed next.

4. Explicit lower certificates

For each line below, define \(G_n=K_n-E(H_n)\). An edge uv means \(\{u,v\}\); vertices are \(0,\ldots,n-1\).

H5:  01
H6:  01 02 12
H7:  01 12 23 34 04
H8:  01 12 23 34 04 07 37 57 67
H9:  04 05 06 08 15 16 17 26 27 28 57 58 78
H10: 04 05 06 08 15 16 17 19 26 27 28 29 57 58 59 78 79 89

Their graph6 encodings as complements are, respectively,

D_?
Ew??
Fhc??
Ghc?Ck
H?bFBId
I?bFBIdXW

The independent lower-bound oracle fixes the least vertex of a prospective cycle, removes reversal symmetry, enumerates every Hamilton cycle on every vertex subset, and compares all edge masks on that subset. It counts every simple cycle exactly once. Its checksums for \(G_1,\ldots,G_{10}\) are

0, 0, 1, 7, 22, 52, 196, 454, 1273, 3300 cycles

and it finds no edge-disjoint pair on a common vertex set. Every candidate edge count and graph6 string is recomputed from the explicit edge lists. [d]

5. Exhaustive upper verification

For each \(n=5,\ldots,10\), and for every missing-edge count smaller than the table's certificate, nauty-geng 2.8.8 generated one representative of every unlabeled complement \(H\). The checker then:

1. decodes graph6, including its order byte;
2. asserts the decoded edge count and re-encodes the graph as a round trip;
3. searches exactly for a witness on 5 vertices, then 6, then 7;
4. uses a separate DFS Hamilton-cycle oracle from size 8 onward if necessary;
5. validates both returned cycles edge by edge and checks equality of their

vertex sets and disjointness of their edge masks.

For seven vertices, all 360 Hamilton cycles of \(K_7\) are generated from scratch. Their disjoint pairs give 465 possible unused-edge masks and 14,802 distinct submasks, yielding an exact constant-time lookup. No precomputed graph catalogue is used for the cycle property.

The completed run was:

| \(n\) | denser unlabeled complements checked | witness sizes (first/minimum size) | |---:|---:|---| | 5 | 1 | \(5:1\) | | 6 | 4 | \(5:3,\ 6:1\) | | 7 | 19 | \(5:15,\ 6:4\) | | 8 | 436 | \(5:286,\ 6:120,\ 7:30\) | | 9 | 12,256 | \(5:8255,\ 6:3392,\ 7:601,\ 8:8\) | | 10 | 906,265 | \(5:604498,\ 6:259544,\ 7:41823,\ 8:400\) |

Total: 918,981 unlabeled complements. Every one had a validated forbidden pair, and in fact every denser graph in these ranges already has such a pair on at most eight vertices. [d]

The trust boundary is explicit: completeness up to isomorphism relies on the standard nauty-geng generator. All later property tests are in the standard-library Python checker. This is not presented as a hand proof of the \(n=7,\ldots,10\) upper bounds.

During development, a fast prototype mistakenly read graph6's order byte as edge data. Its witness distribution was discarded. The original independent NetworkX parse had already produced the same extremal values; the corrected from-scratch parser then reproduced them. The final verifier prevents this specific failure with an order assertion, exact edge-count assertion, and a graph6 round trip on every generated graph.

6. Reproduction

Standalone verifier:

runs/erdos585_wave9t_reverify.py

Run from the repository root:

python runs/erdos585_wave9t_reverify.py

Requirements are Python 3.10+ and nauty-geng. On this VM the complete run took 162.49 seconds and ended with:

total complements checked=918981; witness_sizes={5:613058,6:263061,7:42454,8:408}
F(1)=0, F(2)=1, F(3)=3, F(4)=6, F(5)=9, F(6)=12, F(7)=16, F(8)=19, F(9)=23, F(10)=27
VERIFIED in 162.49s

python -m py_compile and git diff --check also pass.

7. What remains and the precise next wall

The asymptotic problem remains open. The regular-subgraph result alone does not close it: a 4-regular graph decomposes into two 2-factors, but the factors need not be single spanning cycles. The missing structural step is a method, at the \(O(n\log\log n)\) density scale, that merges the components of two edge-disjoint 2-factors into two Hamilton cycles on one common subset. CJMM obtain the needed control only after polylogarithmic-density regularisation, expansion, and absorption. Improving that machinery to the \(\log\log n\) scale is the exact asymptotic bottleneck exposed by the known results. [c]

For the next finite case, adding a degree-three vertex to \(G_{10}\) gives \(F(11)\geq30\) elementary-rigorously. Proving \(F(11)=30\) by the same raw complement enumeration would require checking every 11-vertex complement with at most 24 edges. Brendan McKay's official graph-count table gives a total of 217,670,828 such unlabeled graphs. Scaling the measured 918,981-graph run gives an optimistic 10.7 core-hours, before the more expensive 11-vertex Hamilton searches; a realistic budget is roughly 15–30 core-hours. That computation was deliberately not run on this box. A SAT/ILP formulation with lazy forbidden-union cuts or a canonical search specialised to complements is the appropriate next step. [c/d]

PARTIAL: Exact computational values F(1..10)=0,1,3,6,9,12,16,19,23,27 are certified with explicit lower graphs and 918,981 exhaustive upper checks; the asymptotic gap remains open.