Reused writeup on Math-861 (gpt pro 5.2)

Erdős Problem 585 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/585

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/585.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/585.tex.

FORMAL RESTATEMENT.

For $n\ge 1$, let $m(n)$ be the maximum number of edges in a simple undirected graph $G$ on $n$ vertices with the following forbidden configuration:

There do not exist two cycles $C_1,C_2\subseteq G$ such that \[ V(C_1)=V(C_2)\quad\text{and}\quad E(C_1)\cap E(C_2)=\varnothing. \] (Each $C_i$ is a simple cycle; equality of vertex sets means each is a Hamilton cycle on that vertex set.)

Question: determine/estimate the growth of $m(n)$.

QUICK LITERATURE/CONTEXT CHECK.

I will not use any literature beyond what is explicitly quoted in the problem statement: a construction with $\gg n\log\log n$ edges and an upper bound $n(\log n)^{O(1)}$ are mentioned there.

ATTACK PLAN.

Proof-track ideas. $1$ Identify small unavoidable subgraphs: show that high density forces two edge-disjoint cycles on some vertex set. $2$ Try Turán-type reductions: show the forbidden configuration implies forbidding some complete graph or other dense pattern, yielding an $O(n^2)$ upper bound.

Disproof/construction track ideas. $1$ Explicit sparse constructions with no $4$-regular subgraphs (as referenced in the problem statement) plausibly avoid the forbidden configuration. $2$ For small $n$, brute force compute $m(n)$ exactly to understand the finite extremals.

Here I only prove easy structural upper bounds (quadratic) and compute $m(n)$ for $n\le 7$.

WORK.

Lemma 585.1 (vacuity for $n\le 4$ and exact small $n$ behavior). If $n\le 4$, then no graph on $n$ vertices contains two edge-disjoint cycles with the same vertex set. Consequently $m(n)=\binom n2$ for $n\le 4$. If $n=5$, then the forbidden configuration occurs if and only if $G\cong K_5$, hence $m(5)=9$.

Proof. A cycle uses at least $3$ vertices. If $n\le 4$, then the only possible vertex sets of cycles have size $3$ or $4$. On $3$ vertices the complete graph has only $3$ edges, so it cannot contain two edge-disjoint $3$-cycles (which would require $6$ edges). On $4$ vertices there are at most $6$ edges, while two edge-disjoint $4$-cycles would require $8$ distinct edges; impossible. Thus the forbidden configuration cannot occur for $n\le 4$, so the complete graph $K_n$ is allowed and $m(n)=\binom n2$.

For $n=5$, any cycle with vertex set of size $5$ is a $5$-cycle using $5$ edges. Two edge-disjoint $5$-cycles on the same vertex set would require $10$ distinct edges. But $10$ is the total number of edges on $5$ vertices, so such a pair exists if and only if the induced subgraph on those $5$ vertices is $K_5$, i.e. $G$ contains a $K_5$ subgraph. Since $n=5$, that means $G\cong K_5$. Therefore, among $5$-vertex graphs, exactly $K_5$ is forbidden, so the maximum allowed edge count is $9$. $\square$

Lemma 585.2 ($K_5$ forces the forbidden configuration; Turán bound for $K_5$-free graphs). The complete graph $K_5$ contains two edge-disjoint cycles with the same vertex set. Therefore, any graph $G$ counted by $m(n)$ is $K_5$-free. Moreover, any $K_5$-free graph on $n$ vertices has at most \[ \left\lfloor \frac{3n^2}{8}\right\rfloor \] edges.

Proof (two parts).

Part A: $K_5$ contains two edge-disjoint $5$-cycles on the same vertex set. Label the vertices of $K_5$ by $0,1,2,3,4$. Consider the two cycles \[ C_1: 0-1-2-3-4-0,\qquad C_2: 0-2-4-1-3-0. \] Their edge sets are \[ E(C_1)=\{01,12,23,34,40\},\qquad E(C_2)=\{02,24,41,13,30\}. \] These are disjoint sets of edges, and both cycles use all five vertices. Hence $K_5$ contains the forbidden configuration. Thus any graph without the forbidden configuration must be $K_5$-free.

Part B: $K_5$-free graphs have at most $\lfloor 3n^2/8\rfloor$ edges (a self-contained Turán argument for $r=4$). Let $G$ be a $K_5$-free graph on $n$ vertices with the maximum possible number of edges. We first show that $G$ must be complete multipartite, and then that it has at most $4$ parts.

Step 1 (Zykov symmetrization to get a complete multipartite graph). Suppose there exist two nonadjacent vertices $u\ne v$ with different neighborhoods: $N(u)\ne N(v)$. Construct a new graph $G'$ on the same vertex set by deleting all edges incident to $u$ and then joining $u$ to exactly the vertices in $N(v)$. Equivalently, $u$ becomes a "clone" of $v$ (they have identical neighborhoods).

Claim: $e(G')\ge e(G)$. Indeed, the new degree of $u$ equals $\deg_G(v)$. Since $u$ and $v$ were nonadjacent and neighborhoods differ, we have either $\deg_G(v)>\deg_G(u)$ or $\deg_G(v)<\deg_G(u)$. If $\deg_G(v)\ge \deg_G(u)$ then cloning cannot decrease edges. If $\deg_G(v)<\deg_G(u)$ we instead clone $v$ to $u$. In either case, we can perform a cloning operation on some nonadjacent pair without decreasing the edge count.

Claim: $G'$ remains $K_5$-free. Any $K_5$ in $G'$ that does not include $u$ would already be a $K_5$ in $G$. If a $K_5$ in $G'$ includes $u$, then the other four vertices must all lie in $N_{G'}(u)=N_G(v)$. Those four vertices form a $K_4$ in $G'[N_G(v)]$, hence also in $G[N_G(v)]$. But then in $G$, the vertex $v$ together with that $K_4$ would form a $K_5$, contradiction. So $G'$ is $K_5$-free.

By repeating this operation, we obtain a $K_5$-free graph with at least as many edges as $G$ in which every pair of nonadjacent vertices have identical neighborhoods. In such a graph, "nonadjacent" is an equivalence relation: if $x$ is nonadjacent to $y$, then $N(x)=N(y)$, and then any $z$ nonadjacent to $y$ has $N(z)=N(y)$, hence $z$ is also nonadjacent to $x$. Thus the vertex set partitions into independent sets (equivalence classes), and vertices from different classes are adjacent to each other. Therefore the graph is complete multipartite.

Step 2 (at most four parts). If a complete multipartite graph has at least $5$ parts, then choosing one vertex from each of five parts yields a $K_5$ (since all cross edges are present). Hence a $K_5$-free complete multipartite graph has at most $4$ parts. So $G$ is a complete $4$-partite graph with part sizes $n_1,n_2,n_3,n_4$ summing to $n$ (allowing some $n_i=0$). Its number of edges is \[ e(G)=\sum_{1\le i<j\le 4} n_i n_j =\frac12\left(\left(\sum_{i=1}^4 n_i\right)^2-\sum_{i=1}^4 n_i^2\right) =\frac12\left(n^2-\sum_{i=1}^4 n_i^2\right). \] To maximize $e(G)$ for fixed $n$, we must minimize $\sum n_i^2$. A standard convexity/averaging argument shows that $\sum n_i^2$ is minimized when the $n_i$ are as equal as possible: if $n_i\ge n_j+2$, then replacing $(n_i,n_j)$ by $(n_i-1,n_j+1)$ decreases the sum of squares because \[ (n_i-1)^2+(n_j+1)^2-(n_i^2+n_j^2)= -2(n_i-n_j)+2<0. \] Iterating, we reach a balanced partition with $n_i\in\{\lfloor n/4\rfloor,\lceil n/4\rceil\}$. In that balanced case one checks directly that \[ \sum_{i=1}^4 n_i^2\ge 4\left(\frac n4\right)^2=\frac{n^2}{4} \] (with equality when $4\mid n$). Hence \[ e(G)=\frac12\left(n^2-\sum n_i^2\right)\le \frac12\left(n^2-\frac{n^2}{4}\right)=\frac{3n^2}{8}. \] Since $e(G)$ is an integer, $e(G)\le\lfloor 3n^2/8\rfloor$. $\square$

Fast reality check (exact values for $n\le 7$ by brute force).

I exhaustively enumerated all graphs on $n\le 7$ labeled vertices and tested whether they contain two edge-disjoint cycles with the same vertex set. The resulting exact maxima are: \[ \begin{array}{c|ccccccc} n & 1&2&3&4&5&6&7\\\hline m(n) & 0&1&3&6&9&12&16 \end{array} \] An example achieving $m(6)=12$ is $K_6$ with the triangle on vertices $\{3,4,5\}$ deleted. An example achieving $m(7)=16$ is $K_7$ with the five edges $\{25,26,34,36,45\}$ deleted (in the vertex labeling $0,1,2,3,4,5,6$).

VERIFICATION.

Lemma 585.2 Part A. The two $5$-cycles listed are easily checked to be edge-disjoint and spanning.

Lemma 585.2 Part B. The symmetrization step preserves $K_5$-freeness because any $K_5$ using the cloned vertex would imply a $K_4$ inside a neighborhood, which would create a $K_5$ with the original vertex. The balancing step uses an explicit decrease in sum of squares and is therefore rigorous.

Computation. The brute force check treated the forbidden configuration as: there exists a vertex subset $S$ such that the induced subgraph on $S$ contains two edge-disjoint Hamilton cycles. It is exact for $n\le 7$.

FINAL.

UNRESOLVED

(i) Strongest proved partial result: any graph avoiding the forbidden configuration is $K_5$-free and hence has at most $\lfloor 3n^2/8\rfloor$ edges (Lemma 585.2). Exact values are computed for $n\le 7$ with $m(7)=16$.

(ii) First gap (crisp): improve the crude quadratic upper bound to match the known near-linear (polylog) upper bounds, i.e. prove $m(n)=o(n^2)$ (or even $m(n)=n(\log n)^{O(1)}$) without importing heavy machinery.

(iii) Top 3 next moves: 1. Find a purely combinatorial mechanism forcing two edge-disjoint Hamilton cycles on some vertex set once $e(G)$ exceeds $Cn\log^C n$. 2. Strengthen the "$K_5$-free" observation: identify a much sparser forbidden family implied by the two-cycle condition and prove a sharp extremal bound for that family. 3. Computation: for $n=8,9$ (where full enumeration is too large), use SAT/ILP or backtracking to search for dense examples and guess the extremal structure.

(iv) Minimal counterexample structure (to a conjectured near-linear upper bound): would be a graph with $\omega(n)$ edges but arranged so that every vertex subset supporting a Hamilton cycle supports at most one edge-disjoint Hamilton cycle; heuristically this suggests avoiding any reasonably regular dense subgraph, e.g. graphs engineered to have no $4$-regular subgraphs on any vertex set.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.