Erdős Problem #642

Problem 642 --- Round 2

Let $f(n)$ be the maximum number of edges in an $n$-vertex simple graph $G$ with the property that every cycle $C$ in $G$, with vertex set $S:=V(C)$, has fewer than $|S|$ diagonals. Equivalently (used already in Round 1), every cycle vertex set $S$ satisfies \[ |E(G[S])|<2|S|. \] Indeed, a cycle on $S$ contributes exactly $|S|$ edges, so the number of diagonals is $|E(G[S])|-|S|$.

1) ROUND-2 OBJECTIVE

I pursue path (C): isolate a structural obstruction and prove a stronger theorem, rather than restart from scratch.

Round 1 established only the linear lower bound $f(n)\ge 2n-2$ via graphs of arboricity at most $2$, while the best known general upper bound remains polylogarithmically superlinear. The most promising next step is therefore to push the lower bound beyond arboricity $2$ and to understand the limits of the most natural dense construction paradigm.

The new goal of this round is twofold:

1. construct a denser infinite family satisfying the diagonal condition, and
2. prove that this family is optimal inside the natural class "fixed graph joined to an independent set."

2) Round-1 FOUNDATION USED

I use the following Round-1 facts without reproving them.

1. The reformulation above: to verify the condition, it is enough to show that every induced subgraph on the vertex set of a cycle has fewer than twice as many edges as vertices.
2. The Round-1 construction showing $f(n)\ge 2n-2$ using arboricity at most $2$.
3. The status gap from Round 1: the problem is unresolved in general, and the best published upper bound is $f(n)=O\!\left(n(\log n)^8\right)$.

3) NEW INSIGHT / TOOL (ROUND-2)

The genuinely new ingredients of this round are:

1. a new explicit family $H_n$ with \[ |E(H_n)|=3n-7, \] which improves the Round-1 lower bound from $2n-2$ to $3n-7$ for every $n\ge 6$;
2. a classification theorem for the natural template \[ J_m(F):=F\vee \overline{K_m}, \] where one joins a fixed finite graph $F$ to an independent set of size $m$;
3. a structural consequence: the diagonal condition is not confined to graphs of arboricity at most $2$; the new family has arboricity exactly $3$ for $n\ge 6$.

4) ATTACK PLAN (ROUND-2)

Round 1 left two precise gaps.

1. Its lower bound came only from arboricity $2$. One must determine whether denser graphs can still satisfy the cycle/diagonal restriction.
2. Even if one finds a denser family, it remains unclear whether that family is merely accidental or is in fact extremal within some natural construction scheme.

The plan is therefore:

1. build a graph on $n$ vertices with about $3n$ edges and prove rigorously that every cycle still has fewer than $|C|$ diagonals;
2. abstract the construction to a general join-template $J_m(F)$;
3. characterize exactly which fixed templates $F$ work for all $m$.

This overcomes the Round-1 obstacle because it both increases the lower bound and explains why the coefficient $3$ arises naturally.

5) WORK (ROUND-2)

5.1. The new construction.

For $n\ge 6$, let \[ A:=\{a_1,a_2,a_3\},\qquad B:=\{b_1,\dots,b_{n-3}\}. \] Define $H_n$ as follows:

1. $B$ is independent;
2. $A$ induces the path $a_1a_2a_3$;
3. every vertex of $A$ is adjacent to every vertex of $B$.

So $H_n$ is the join of $P_3$ with an independent set of size $n-3$. Its number of edges is \[ |E(H_n)|=3(n-3)+2=3n-7. \]

5.2. Main new lower bound.

Theorem 5.1. For every $n\ge 6$, the graph $H_n$ satisfies the diagonal condition. Consequently, \[ f(n)\ge 3n-7\qquad (n\ge 6). \]

Proof. Let $C$ be any cycle in $H_n$, and let $S:=V(C)$. Write \[ a:=|S\cap A|,\qquad b:=|S\cap B|. \] Since $B$ is independent, no two vertices of $B$ can be consecutive on the cycle $C$. Hence \[ b\le a. \] Also $a\le 3$ because $|A|=3$.

Now count the edges of the induced subgraph $H_n[S]$. Every vertex of $S\cap B$ is joined to every vertex of $S\cap A$, contributing $ab$ edges. Inside $A$, the induced graph is a subgraph of the path $a_1a_2a_3$, so it contributes at most $a-1$ edges. Thus \[ |E(H_n[S])|\le ab+(a-1). \] By the Round-1 reformulation, it is enough to show \[ |E(H_n[S])|<2|S|=2(a+b). \] Since $a\le 3$, there are only two relevant cases.

Case $a=2$. Then $b\le 2$, and therefore \[ |E(H_n[S])|\le 2b+1\le 5<2(2+b). \]

Case $a=3$. Then $b\le 3$, and therefore \[ |E(H_n[S])|\le 3b+2<2(3+b), \] because this inequality is equivalent to $b<4$.

These are all possible cycle-carrying cases. Hence every cycle vertex set $S$ satisfies $|E(H_n[S])|<2|S|$, so every cycle has fewer diagonals than vertices. This proves that $H_n$ is admissible, and therefore \[ f(n)\ge |E(H_n)|=3n-7. \] $\square$

5.3. The new family has arboricity exactly $3$.

Round 1 only produced admissible graphs of arboricity at most $2$. The new family shows that this is not the real barrier.

Corollary 5.2. For every $n\ge 6$, the graph $H_n$ has arboricity exactly $3$.

Proof. Since \[ |E(H_n)|=3n-7>2(n-1) \qquad (n\ge 6), \] Nash--Williams implies $\operatorname{arb}(H_n)\ge 3$. On the other hand, $E(H_n)$ can be partitioned into the following three forests: \[ F_1:=\{a_1b_i:1\le i\le n-3\}\cup\{a_1a_2\}, \] \[ F_2:=\{a_2b_i:1\le i\le n-3\}, \] \[ F_3:=\{a_3b_i:1\le i\le n-3\}\cup\{a_2a_3\}. \] Thus $\operatorname{arb}(H_n)\le 3$, so $\operatorname{arb}(H_n)=3$. $\square$

5.4. Optimality inside the natural join-template class.

The construction above is not ad hoc; it is extremal within a broad and natural family.

For a fixed finite graph $F$ on $t$ vertices and an integer $m\ge 0$, let \[ J_m(F):=F\vee \overline{K_m} \] be the graph obtained from the disjoint union of $F$ and an independent set $I_m$ of size $m$ by adding all edges between $V(F)$ and $I_m$.

Theorem 5.3. The following are equivalent for a finite graph $F$.

1. For every $m\ge 0$, the graph $J_m(F)$ satisfies the diagonal condition.
2. $F$ has at most $3$ vertices and $F$ is a forest.

Consequently, among all admissible graphs of the form $J_m(F)$ on $n$ vertices, the maximum number of edges is $3n-7$, attained by $F=P_3$.

Proof. Write $t:=|V(F)|$.

$(2)\Rightarrow(1)$. Assume $F$ is a forest on at most $3$ vertices. Let $S$ be the vertex set of a cycle in $J_m(F)$, and write \[ a:=|S\cap V(F)|,\qquad b:=|S\cap I_m|. \] Because $I_m$ is independent, no two vertices of $S\cap I_m$ can be consecutive on the cycle, so again $b\le a$. Also $a\le t\le 3$.

Inside $S$, the edges are of two kinds:

1. all $ab$ cross-edges between $S\cap V(F)$ and $S\cap I_m$;
2. the edges of the induced forest $F[S\cap V(F)]$, at most $a-1$ of them.

Hence \[ |E(J_m(F)[S])|\le ab+(a-1). \] Exactly as in the proof of Theorem 5.1, this is $<2(a+b)$ for all possible cycle-carrying cases $a=2,3$. So every cycle in $J_m(F)$ has fewer diagonals than vertices.

$(1)\Rightarrow(2)$. Assume instead that $J_m(F)$ satisfies the diagonal condition for every $m$. Take $m=t$, and let $I_t=\{x_1,\dots,x_t\}$ be the independent side. Choose an arbitrary ordering $v_1,\dots,v_t$ of $V(F)$. Because every $x_i$ is adjacent to every $v_j$, the alternating cycle \[ v_1x_1v_2x_2\cdots v_tx_tv_1 \] is a Hamiltonian cycle in the induced subgraph on $V(F)\cup I_t$. Therefore the diagonal condition gives \[ |E(F)|+t^2<2(2t)=4t. \] So \[ |E(F)|<4t-t^2. \] Since $|E(F)|\ge 0$, this forces $t\le 3$. If $t=3$, then $|E(F)|<3$, so $|E(F)|\le 2$, and any graph on $3$ vertices with at most $2$ edges is a forest. If $t=2$, every graph on $2$ vertices is a forest. If $t\le 1$, the statement is trivial. Thus $F$ is a forest on at most $3$ vertices.

Finally, if $J_m(F)$ has $n=t+m$ vertices, then \[ |E(J_m(F))|=tm+|E(F)|. \] By the classification above, the largest possible value occurs for $t=3$ and $|E(F)|=2$, namely when $F=P_3$. This gives \[ |E(J_m(F))|\le 3m+2=3(n-3)+2=3n-7. \] Hence $H_n=J_{n-3}(P_3)$ is optimal within the whole join-template class. $\square$

5.5. Supplementary exact small values (computer-assisted, not used above).

An exhaustive search over all $2^{\binom{n}{2}}$ labeled graphs for $n\le 7$ gives: \[ f(1)=0,\quad f(2)=1,\quad f(3)=3,\quad f(4)=6,\quad f(5)=9,\quad f(6)=11,\quad f(7)=14. \] In particular, the new lower bound $f(n)\ge 3n-7$ is already exact for $n=6,7$.

6) ADVERSARIAL VERIFICATION

I now check the new arguments against the most likely failure points.

(i) Did I use a stronger condition than the problem asks?

No. I used the Round-1 equivalence: for a cycle on vertex set $S$, the number of diagonals is $|E(G[S])|-|S|$. So proving $|E(G[S])|<2|S|$ for every cycle vertex set is exactly the required condition.

(ii) Why is $b\le a$ valid?

Because the independent side has no internal edges. Along any cycle, two vertices from the independent side cannot be consecutive, so the number of such vertices is at most the number of vertices from the other side.

(iii) Did the proof accidentally rely on the whole induced subgraph being a cycle?

No. The induced subgraph may have extra edges. I counted all induced edges on $S$ and proved they are still fewer than $2|S|$. That is exactly the right quantity.

(iv) In Theorem 5.3, does the alternating Hamiltonian cycle really exist for arbitrary $F$?

Yes. The cycle \[ v_1x_1v_2x_2\cdots v_tx_tv_1 \] uses only cross-edges between $V(F)$ and $I_t$, and all such edges are present by definition of the join. No edges of $F$ are needed for that cycle.

(v) Could a template with $|V(F)|\ge 4$ still work because the bad $2t$-vertex set is not induced-Hamiltonian?

No. The alternating cycle above is already a Hamiltonian cycle in that induced subgraph, so the obstruction is genuine.

(vi) Did I really go beyond Round 1?

Yes, in two separate ways. First, the lower bound improved from $2n-2$ to $3n-7$. Second, the new family has arboricity exactly $3$, so Round-1's arboricity-$2$ sufficient condition is not close to being necessary.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The problem remains open in full generality, but this round gives a genuine advance beyond Round 1:

1. I proved the new lower bound \[ f(n)\ge 3n-7\qquad (n\ge 6), \] via the explicit family $H_n=P_3\vee \overline{K_{n-3}}$.
2. I proved that this family has arboricity exactly $3$, showing that admissible graphs need not have arboricity at most $2$.
3. I classified all admissible graphs in the broad join-template class $J_m(F)$, and proved that $3n-7$ is best possible within that whole class.
4. I recorded exact values for $f(n)$ for $n\le 7$ by exhaustive search.

A sharp next conjecture suggested by the new evidence is: \[ f(n)=3n-7\qquad \text{for all sufficiently large }n. \] I have not proved this, so the global problem remains unresolved.

8) COMPLETION ESTIMATE

COMPLETION: 60%

9) REFERENCES

1. N. Draganić, A. Methuku, D. Munhá Correia, and B. Sudakov, Cycles with many chords, Random Structures & Algorithms 65$1$ $2024$, 3--16.

2. N. Draganić and A. Girão, Cycles with almost linearly many chords, arXiv:2601.08769, 2026.

Erdős Problem #642: independent continuation

Date: 23 September 2026. Source versions read in full: 642.tex in gpt_pro_5.4.

1) OBJECTIVE AND AUDIT

Let $f(n)$ maximize edges subject to every cycle having fewer chords than vertices. Equivalently, a cycle on vertex set $S$ must satisfy $e(G[S])<2|S|$. The original question is $f(n)=O(n)$. The supplied join construction gives $f(n)\ge3n-7$ for $n\ge6$. Its classification of fixed cores valid for every independent-set size does not classify all admissible graphs.

2) GLUING AND AN EXACT ASYMPTOTIC REDUCTION

Identify one vertex of two admissible graphs, with no other new edges. Every simple cycle lies wholly in one of the two graphs: a cycle traversing both would have to visit the shared vertex twice. Thus the resulting graph is admissible, and \[ f(a+b-1)\ge f(a)+f(b). \] Set $h(m)=f(m+1)$. It is nonnegative and superadditive. For any fixed $q$, writing $m=tq+r$ gives $h(m)\ge t h(q)$, so \[ \liminf_{m\to\infty}\frac{h(m)}m\ge\frac{h(q)}q. \] Taking the supremum over $q$ and comparing with the trivial upper bound by that supremum proves the extended-real limit \[ \boxed{\lim_{n\to\infty}\frac{f(n)}{n-1} =\sup_{v\ge2}\frac{f(v)}{v-1}\in[3,\infty].} \tag{1} \] This also proves existence of the extended-real limit of $f(n)/n$. The lower endpoint follows from $3n-7$.

3) CONSEQUENCES FOR A POSSIBLE PROOF

The original linear-bound problem is exactly whether the supremum in $1$ is finite. It is enough to bound $e(B)/(|B|-1)$ uniformly over admissible blocks: every cycle belongs to a block, edges partition over blocks, and for a connected graph the block quantities $|B|-1$ sum to $n-1$ (bridges count as two-vertex blocks). Conversely any single block with ratio $c$ can be repeated at one shared vertex, producing arbitrarily large admissible graphs with limiting density $c$. In particular, an asymptotic constant $3$ would require the finite inequality $e(G)\le3(|G|-1)$ for every admissible graph. Testing only the three-vertex-core joins cannot establish that inequality.

4) LIMITATION

The limit in $1$ is allowed to be infinite. Its existence does not improve the known near-linear upper bounds or prove the desired uniform block bound.

7) FINAL

UNRESOLVED. A precise asymptotic-density reduction and block obstruction are proved, without a claim of literature novelty. Statement and known-bound record: https://www.erdosproblems.com/642.

8) COMPLETION ESTIMATE

COMPLETION: 10% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem 642

1) FORMAL RESTATEMENT

For an integer $n\ge 1$, let $f(n)$ be the maximum number of edges in an $n$-vertex (simple, undirected) graph $G$ with the property:

For every cycle $C$ in $G$ with vertex set $S:=V(C)$, the number of diagonals of $C$ present in $G$ (i.e., edges of $G[S]$ joining two nonconsecutive vertices of $C$) is strictly less than $|S|$.

Equivalently, for every cycle $C$ of length $\ell$, \[ |E(G[S])| = \ell + \#\{\text{diagonals of $C$ present in }G\} < 2\ell. \] Question. Is it true that $f(n)\ll n$, i.e. $f(n)=O(n)$?

2) QUICK LITERATURE/CONTEXT CHECK

Letting a "diagonal" mean a chord present in the graph, the best published general upper bounds currently are \[ f(n)\ll n^{3/2}\quad\text{(Chen--Erd\H{o}s--Staton, 1996)} \qquad\text{and}\qquad f(n)\ll n(\log n)^8\quad\text{(Dragani\'{c}--Methuku--Munh\'{a} Correia--Sudakov, 2024)}. \] The linear bound remains open.

3) ATTACK PLAN

Provide:

1. A clean linear lower bound construction, to pin down $f(n)$ from below.
2. A structural sufficient condition (in terms of arboricity) guaranteeing the cycle/diagonal property.
3. A summary of what would be needed to close the remaining polylogarithmic gap in the known upper bound.

4) WORK

4.1. A sufficient condition via arboricity.

Recall that the arboricity $\mathrm{arb}(G)$ is the least $a$ such that $E(G)$ can be partitioned into $a$ forests. Equivalently (Nash--Williams), \[\mathrm{arb}(G)=\max_{H\subseteq G,\,|V(H)|\ge 2}\left\lceil\frac{|E(H)|}{|V(H)|-1}\right\rceil.\]

4.2. A linear lower bound: $f(n)\ge 2n-2$ for $n\ge 4$.

We explicitly construct an $n$-vertex graph with $2n-2$ edges satisfying the diagonal condition.

Consequently, \[ f(n)\ge 2n-2\qquad(n\ge 4). \]

4.3. Status summary.

Combining the explicit lower bound with the best current upper bounds yields \[ 2n-2\ \le\ f(n)\ \ll\ n(\log n)^8. \] Closing the gap requires either: (i) improving the upper bound to $O(n)$ by showing that constant average degree already forces a cycle with at least as many chords as vertices, or (ii) constructing graphs with $\omega(n)$ edges in which every cycle has $<\ell$ diagonals.

5) VERIFICATION / SANITY CHECKS

• In a graph of arboricity $\le 2$, every induced subgraph on $\ell$ vertices has at most $2\ell-2$ edges; for cycle vertex sets this forces $\#\text{diagonals}\le \ell-2$.
• The construction produces two edge-disjoint spanning trees for every $n\ge 4$; their union has $2n-2$ edges and arboricity at most $2$.

6) FINAL

UNRESOLVED.

Best partial results/progress achieved here:

• Gave a simple sufficient condition: arboricity $\le 2$ implies the diagonal property.
• Built an explicit extremal-style construction with $2n-2$ edges (for $n\ge 4$), proving $f(n)\ge 2n-2$.
• Summarized the current best known upper bounds and the remaining gap.

Concrete next moves that look most promising:

1. Try to prove a constant-average-degree forcing result: show that if $|E(G)|\ge Cn$ then some cycle has at least $|C|$ diagonals.
2. Alternatively, attempt explicit superlinear constructions satisfying the diagonal condition (e.g. iterated 2-arboric expansions) to refute linearity.
3. Investigate whether random-walk/expander methods used for the $n(\log n)^8$ upper bound can be strengthened to remove the polylog factor.

7) COMPLETION ESTIMATE

COMPLETION: 40%