Dense triangle free graphs with paths of length 3 between every pair of vertices Does there exist an infinite family of dense (i.e. #edges = $m = O(n^2)$) graphs such that they are triangle-free and have a path of length exactly 3 between every pair of vertices?
Best lower bound(of edges) that I can come up with is from the family of Mycielskian graphs which have around $n^{log_2(3)} \approx n^{1.585}$ edges in the limit.
Edit As Misha Lavrov pointed out in the comments the Kneser graph KG(3k-1, k) in limit gives a graph with edges $n^{log_{27/4}(27)} \approx n^{1.726 }$ edges. 
Edit The generalized Kneser graph KG(6k-1, 3k, k) in limit has $n^{log_{8}(54)} \approx n^{1.918}$ edges. This gives an even better lower bound but still not dense. Note that no generalized Kneser graph which is triangle-free will give a dense graph. 
Note that we can take the graphs to maximally triangle-free which implies that they are minimal graphs of diameter 2 i.e. removing any edge increases the diameter from 2 to 3.
 A: Take the graph with vertices $\{0,1,2\}\times(\mathbb Z/3d\mathbb Z)$ and edges:


*

*$(0,i)\sim (1,i+j)$ for $0\leq j\leq d-2$ or $j=d$

*$(1,i)\sim (2,i+j)$ for $0\leq j\leq d-2$ or $j=d$

*$(2,i)\sim (0,i+j+1)$ for $0\leq j\leq d-2$ or $j=d$


This has density about $\tfrac 2 9.$
Note there is a symmetry sending $(0,j),(1,j),(2,j)$ to $(1,j),(2,j),(0,j+1)$ respectively.
Starting from $(0,0),$ paths of length $3$ can reach at least the vertices $(1,j+j'-j'')$ with $j'\neq j''$ and $j,j',j''$ each in $\{0,\dots,d-3,d-2,d\}.$ This lets it reach any vertex of the form $(1,j).$ By symmetry any two vertices whose first co-ordinate is different are connected by a path of length $3.$
For $(0,0)$ to reach a vertex of the form $(0,i)$ by a path of length $3$ it has to go all the way around the first co-ordinate, ending up at $(0,j+j'+j''+1)$ with $j,j',j''$ in $\{0,\dots,d-3,d-2,d\}.$ which lets it reach exactly $(0,1)$ to $(0,3d-1).$ By symmetry, any two different vertices with the same first co-ordinate are connected by a path of length three, and there are no triangles.
