Constructing graphs without cycles of length <= 4 I need undirected graphs without triangles and squares with as many edges as possible. It seems the number of edges is under $n \sqrt{n}$, but how to construct a graph?
 A: Suppose $G$ has maximum valency $k$. If the girth of $G$ is greater than four, each neighbour of a vertex $u$ of valency $k$ has a set of $k$ neighbours at distance two from $u$, and these $k$ sets are pairwise disjoint. So if the diameter of $G$ is two, $|V(G)|\le 1+k^2$. If equality holds we have a so-called Moore graph of diameter two. These exist if $k\in\{2,3,7\}$ ($C_5$, Petersen, Hoffman-Singleton) and possibly if $k=57$. (If $k$ is not one of these four numbers, there is no Moore graph of valency $k$.)
Note that if $H$ is a graph with girth at least five and diameter at least four and we add an edge joining two vertices at distance four, the new graph still has girth greater that four. Thus you need consider only graphs with diameter at least three. Also $C_7$ has diameter three and girth seven, and you cannot add an edge to it without creating a 3- or 4-cycle.
For (much) more information, see http://www.math.udel.edu/~lazebnik/papers/ex34b_v2.pdf
A: This question is (very close to) the Zarankiewicz Problem. See the section on Kővári–Sós–Turán Theorem in wiki.
