we-solve (beta)

Math-5404-A6 · revision r1 · on Math-5404

gpt pro 5.2 attempt on Math-5404, version 4

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 4
  2. Problem (as in 65.tex)
  3. Notation
  4. 1) ROUND-4 OBJECTIVE
  5. 2) Round-3 FOUNDATION USED
  6. 3) NEW INSIGHT / TOOL (ROUND-4)
  7. 4) ATTACK PLAN (ROUND-4)
  8. 5) WORK (ROUND-4)
  9. 6) ADVERSARIAL VERIFICATION
  10. 7) FINAL (EXACTLY ONE)
  11. 8) COMPLETION ESTIMATE (MANDATORY)
  12. 9) REFERENCES

Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 4

Problem (as in 65.tex)

Let $G$ be a (simple) graph with $n$ vertices and $m=kn$ edges. Let \[ 3\le a_1<a_2<\cdots<a_t \] be the distinct cycle lengths occurring in $G$ (so $\{a_1,\dots,a_t\}$ is the cycle-length set of $G$). Define \[ S(G):=\sum_{i=1}^t \frac1{a_i}. \] Question $1$ asks whether $S(G)\gg \log k$ always holds. Question $2$ asks whether, for fixed $(n,m)$, the quantity $S(G)$ is minimized when $G$ is a complete bipartite graph (in particular, for those $(n,m)$ for which some $K_{a,b}$ has $a+b=n$ and $ab=m$).

Round 4 continues the investigation of Question $2$, building on the vetted progress from Rounds 2--3.

Notation

For a graph $G$, write $\mathcal C(G)\subseteq\{3,4,\dots,n\}$ for the set of distinct cycle lengths in $G$, so $S(G)=\sum_{\ell\in\mathcal C(G)}\frac1\ell$.

1) ROUND-4 OBJECTIVE

Path (A): extend the verified "$m=2n-4$" family from Round 3 by proving the next open case $n=13$, i.e. \[ \min\{S(G): |V(G)|=13,\ |E(G)|=22\}=\frac14, \] with an extremal graph given by $K_{2,11}$. This is the most promising next step because Round 3 reduces all $7\le n\le 12$ cases on the line $m=2n-4$ to the absence of $\{C_3,C_4\}$-free graphs, and $n=13$ is the first value where the coarse extremal bound no longer forbids $\{C_3,C_4\}$-free graphs at $m=2n-4$.

2) Round-3 FOUNDATION USED

We rely on the following vetted Round-3 items (not reproved here):
  • $F1$ Cycle spectrum of $K_{a,b}$. For $2\le a\le b$, $\mathcal C(K_{a,b})=\{4,6,\dots,2a\}$, hence \[ S(K_{a,b})=\sum_{j=2}^a\frac1{2j}=\frac12(H_a-1). \] In particular $S(K_{2,b})=\frac14$.
  • $F2$ Two-path injection bound (Round 3 lemma). If $G$ is $\{C_3,C_4\}$-free on $n$ vertices and $m$ edges, then \[ m\ \le\ \frac n2\sqrt{n-1}. \] Equivalently, writing $P_2(G)=\sum_{v}\binom{d(v)}2$ for the number of (unordered-endpoint) $2$-paths, one has $P_2(G)\le \binom n2-m$, and Cauchy--Schwarz yields the displayed bound.
  • $F3$ Exact minimization on the line $m=2n-4$ for $7\le n\le 12$ (Round 3 theorem). For each $7\le n\le 12$ and $m=2n-4$, every $n$-vertex $m$-edge graph satisfies $S(G)\ge \frac14$, and equality is achieved by $K_{2,n-2}$.

3) NEW INSIGHT / TOOL (ROUND-4)

Two new ingredients:
  • $N1$ Max-degree splitting rigidity at $(n,m)=(13,22)$. If $G$ is $\{C_3,C_4\}$-free on $13$ vertices and $22$ edges, then a maximum-degree vertex has degree exactly $4$, and the induced subgraph on the remaining $8$ vertices has exactly $10$ edges and is still $\{C_3,C_4\}$-free.
  • $N2$ Extremal $8$-vertex lemma. Any $\{C_3,C_4\}$-free graph on $8$ vertices with $10$ edges contains a $6$-cycle (and hence contains cycle lengths $5$ and $6$).

4) ATTACK PLAN (ROUND-4)

Round 3's extremal-edge obstruction stops at $n=13$ because the bound $F2$ allows $m=22$.

To close the gap:

  1. Show that any $\{C_3,C_4\}$-free $G$ on $(n,m)=(13,22)$ forces an induced $\{C_3,C_4\}$-free subgraph $B$ on $8$ vertices with $10$ edges (new rigidity $N1$).
  2. Prove structurally that every such $B$ contains a $6$-cycle (new lemma $N2$).
  3. Conclude: if $G$ has a $C_3$ or $C_4$ then $S(G)\ge \frac14$; if $G$ is $\{C_3,C_4\}$-free then it contains $C_5$ and $C_6$, so $S(G)\ge \frac15+\frac16>\frac14$. Therefore the minimum is $\frac14$, achieved by $K_{2,11}$.

5) WORK (ROUND-4)

Lemma (Max-degree splitting rigidity at $(13,22)$): Let $G$ be a $\{C_3,C_4\}$-free graph with $|V(G)|=13$ and $|E(G)|=22$. Then $\Delta(G)=4$. Moreover, for a vertex $v$ of degree $4$ and $A:=N(v)$, the induced subgraph $B:=G\big[V(G)\setminus(\{v\}\cup A)\big]$ has $|V(B)|=8$ and $|E(B)|=10$, and is $\{C_3,C_4\}$-free.
Proof: Let $v$ be a vertex of maximum degree $\Delta=\Delta(G)$, and set $A:=N(v)$ and $B:=V(G)\setminus(\{v\}\cup A)$, so $|A|=\Delta$ and $|B|=12-\Delta$.

Because $G$ is triangle-free, $A$ is an independent set. Because $G$ is $C_4$-free, no vertex of $B$ can have two neighbors in $A$ (else $v$ together with those two neighbors and the vertex in $B$ forms a $4$-cycle). Hence the number of edges between $A$ and $B$ is at most $|B|=12-\Delta$.

Write $e(B):=|E(G[B])|$. Then \[ 22 \;=\; |E(G)| \;\le\; |E(\{v\},A)| + |E(A,B)| + e(B) \;\le\; \Delta + (12-\Delta) + e(B), \] so $e(B)\ge 10$.

The induced subgraph $G[B]$ is still $\{C_3,C_4\}$-free, so by the Round-3 bound $F2$, \[ e(B)\ \le\ \frac{|B|}{2}\sqrt{|B|-1}\ =\ \frac{12-\Delta}{2}\sqrt{11-\Delta}. \] If $\Delta\ge 5$, then $|B|\le 7$ and the right-hand side is $<9$, contradicting $e(B)\ge 10$. Thus $\Delta\le 4$.

On the other hand, $2|E(G)|/|V(G)|=44/13>3$, so $\Delta\ge 4$. Hence $\Delta=4$, so $|B|=8$. Then the same bound gives $e(B)\le \frac82\sqrt7<11$, hence $e(B)\le 10$. Together with $e(B)\ge 10$, we get $e(B)=10$.

Finally, $G[B]$ is induced, hence $\{C_3,C_4\}$-free as claimed. ∎

Lemma (Extremal $8$-vertex lemma): Let $H$ be a $\{C_3,C_4\}$-free graph with $|V(H)|=8$ and $|E(H)|=10$. Then $H$ contains a $6$-cycle. In particular, $5,6\in\mathcal C(H)$.
Proof: We proceed in steps.

Step 1: $\delta(H)\ge 2$ and $H$ is connected. If $H$ has a vertex $x$ of degree $\le 1$, then $H-x$ has $7$ vertices and at least $9$ edges. But $H-x$ is still $\{C_3,C_4\}$-free, contradicting the Round-3 bound $F2$ for $n=7$: \[ |E(H-x)|\le \frac72\sqrt6<9. \] Hence $\delta(H)\ge 2$.

If $H$ were disconnected, write $H=H_1\cup H_2$ with $|V(H_i)|=n_i\ge 1$ and $n_1+n_2=8$. Each $H_i$ is $\{C_3,C_4\}$-free, so by $F2$, \[ |E(H)|=|E(H_1)|+|E(H_2)|\ \le\ \frac{n_1}{2}\sqrt{n_1-1}+\frac{n_2}{2}\sqrt{n_2-1}. \] For $1\le n_1\le 7$ the right-hand side is $<10$, contradicting $|E(H)|=10$. So $H$ is connected.

Step 2: $H$ is not bipartite, hence contains a $5$-cycle. If $H$ were bipartite with parts $(X,Y)$, $|X|=p\le q=|Y|$ and $p+q=8$, then $H$ being $C_4$-free implies that any two vertices of $Y$ have at most one common neighbor in $X$. Equivalently, \[ \sum_{x\in X}\binom{d(x)}2 \ \le\ \binom{q}{2}. \] Let $m:=|E(H)|=\sum_{x\in X}d(x)$. By Cauchy--Schwarz, $\sum_{x\in X}d(x)^2\ge m^2/p$, hence \[ \sum_{x\in X}\binom{d(x)}2 = \frac12\Big(\sum_{x\in X}d(x)^2 - m\Big)\ \ge\ \frac12\Big(\frac{m^2}{p}-m\Big). \] Therefore $\frac12(\frac{m^2}{p}-m)\le \binom q2$, i.e. \[ \frac{m^2}{p}-m \ \le\ q(q-1). \] For $(p,q)=(4,4)$ this gives $m\le 9$, and for $(p,q)=(3,5),(2,6),(1,7)$ it gives $m\le 9,8,7$ respectively. In all cases, $m\le 9$, contradicting $m=10$. Thus $H$ is not bipartite, so it contains an odd cycle; since $H$ is $\{C_3,C_4\}$-free, the shortest odd cycle has length $5$, hence $H$ contains a $5$-cycle $C$.

Step 3: Structure around the $5$-cycle. Let $C=v_0v_1v_2v_3v_4v_0$ be a $5$-cycle in $H$, and let $X:=V(H)\setminus V(C)$, so $|X|=3$.

Claim: each $x\in X$ has at most one neighbor on $C$.

Indeed, if $x$ is adjacent to two consecutive vertices $v_i,v_{i+1}$ on $C$, then $xv_iv_{i+1}x$ is a triangle, forbidden. If $x$ is adjacent to two nonconsecutive vertices $v_i,v_{i+2}$, then the path $v_i v_{i+1} v_{i+2}$ together with $x$ gives a $4$-cycle $v_i v_{i+1} v_{i+2} x v_i$, also forbidden. So the claim holds.

Now decompose edges: \[ 10=|E(H)|=|E(C)| + |E(C,X)| + |E(H[X])| = 5 + e_{CX} + e_X, \] where $e_{CX}:=|E(C,X)|$ and $e_X:=|E(H[X])|$. Since $H$ is triangle-free, $H[X]$ has at most $2$ edges (a path on $3$ vertices), so $e_X\le 2$, hence $e_{CX}\ge 3$. By the claim, each vertex of $X$ contributes at most one edge to $C$, so $e_{CX}\le 3$. Therefore $e_{CX}=3$ and $e_X=2$.

Consequently, $H[X]$ is a path $x-y-z$, and each of $x,y,z$ has exactly one neighbor on $C$. Write these neighbors as $a,b,c\in V(C)$ with $xa, yb, zc\in E(H)$.

Step 4: Forcing a $6$-cycle. Consider the edge $xy$. Because $H$ is triangle-free, $a\neq b$. If $a$ were adjacent to $b$ on the $5$-cycle $C$, then $a-x-y-b-a$ would be a $4$-cycle, impossible. So $a$ and $b$ are nonadjacent vertices on $C$. In a $5$-cycle, two nonadjacent vertices are connected by two internally disjoint paths of lengths $2$ and $3$. Let $P$ be the longer $a$--$b$ path in $C$, of length $3$. Then the closed walk \[ a-x-y-b \cup P \] is a simple cycle of length $1+1+1+3=6$ (all vertices are distinct: $x,y\notin V(C)$ and $P$ uses only vertices of $C$). Thus $H$ contains a $6$-cycle, completing the proof. ∎

Theorem (The case $(n,m)=(13,22)$): Among graphs $G$ with $|V(G)|=13$ and $|E(G)|=22$, one has \[ S(G)\ \ge\ \frac14. \] Moreover, equality holds for $K_{2,11}$, so the minimum value of $S(G)$ is $\frac14$ and a complete bipartite graph is extremal.
Proof: Let $G$ be a graph on $13$ vertices with $22$ edges.

If $G$ contains a $4$-cycle, then $4\in\mathcal C(G)$ and $S(G)\ge \frac14$. If $G$ contains a triangle, then $3\in\mathcal C(G)$ and $S(G)\ge \frac13>\frac14$. So we may assume $G$ is $\{C_3,C_4\}$-free.

By Lemma lem:13-22-rigidity, $G$ contains an induced $\{C_3,C_4\}$-free subgraph $B$ on $8$ vertices with $10$ edges. By Lemma lem:8-10-has-C6, $B$ contains a $5$-cycle and a $6$-cycle. Therefore $5,6\in\mathcal C(G)$, hence \[ S(G)\ \ge\ \frac15+\frac16\ >\ \frac14. \] So in all cases $S(G)\ge \frac14$.

Finally, $K_{2,11}$ has $13$ vertices and $22$ edges, and by $F1$ its cycle-length set is $\{4\}$, so $S(K_{2,11})=\frac14$. ∎

6) ADVERSARIAL VERIFICATION

We stress-check the new arguments.
  • Inheritance of forbidden cycles. Every induced subgraph of a $\{C_3,C_4\}$-free graph is $\{C_3,C_4\}$-free, so applying $F2$ to $G[B]$ in Lemma lem:13-22-rigidity is valid.
  • Edge decomposition in Lemma lem:13-22-rigidity. The key inequality $|E(A,B)|\le |B|$ uses only that each $b\in B$ has at most one neighbor in $A$ (else a $4$-cycle through $v$), which follows from $C_4$-freeness. No hidden regularity is assumed.
  • Lemma lem:8-10-has-C6, Step 3 ("at most one neighbor on $C$"). On a $5$-cycle, two distinct vertices are either adjacent (creating a triangle with $x$) or at distance $2$ (creating a $4$-cycle $v_i v_{i+1} v_{i+2} x v_i$). The argument uses only the edges of $C$.
  • Lemma lem:8-10-has-C6, Step 4 (forming a simple $6$-cycle). The "long" $a$--$b$ path on $C$ has length $3$ and is internally disjoint from $\{a,b\}$. Since $x,y\notin V(C)$, the resulting cycle uses exactly six distinct vertices, hence is a genuine $C_6$.
  • Quantifier boundary. Theorem thm:13-22 partitions cases by existence of $C_3$ or $C_4$; these exhaust possibilities because $|E(G)|>|V(G)|-1$ forces at least one cycle, so $S(G)$ is always well-defined.

No contradictions with Round-3 results were found; the new theorems strictly extend the $m=2n-4$ family from $7\le n\le 12$ to $n=13$.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

We proved the conjectured minimization statement for the new parameter pair $(n,m)=(13,22)$ (equivalently, the next case on the line $m=2n-4$ where the complete bipartite candidate is $K_{2,11}$). The full "complete bipartite minimizes $S(G)$ for all $(n,m)$" conjecture remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 82%.

9) REFERENCES

Only Round-3 internal results were used:
  • Round 3 lemma: $\{C_3,C_4\}$-free edge bound $m\le \frac n2\sqrt{n-1}$.
  • Round 3 theorem: exact minimization on $m=2n-4$ for $7\le n\le 12$.