Maximum edges in a square free graph Square free graph : Graphs with minimum cycle length greater than 4.
Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order $O(n^2)$?
How does the answer change if max_degree(G) = d ($>1$)?
EDIT: Out of curiosity, what is the maximum number of edges with $n$ vertices, when  we limit the girth of the graph to $l$.
Thanks in advance!
 A: According the Abstract (postscript), Zoltan Füredi proves that for $q \ge 25$, a $C_4$-free graph on $q^2 + q + 1$ vertices has at most $\frac{1}{2}q(q+1)^2$ edges, which implies $\frac{1}{2}n^{3/2}$ maximum edges asymptotically (for $n$ nodes). Füredi also describes the graphs which attain his upper bound in terms of finite projective planes. [NB: After viewing the paper itself and references to it, the correct upper bound is $\frac{1}{2}q(q+1)^2$ edges, at slight variance with the Abstract.]
His papers are available for PDF and PS download at this link, item 148., which includes some longer (published and unpublished) versions.
A: The maximum number of edges in any finite simple graph is of the order $O(n^2)$ so your guess is true, I suppose, but trivially so. 
Anyway, your question lies in the area of "extremal graph theory." There is a book by Bollobás with that title which I haven't read but would likely be a good place to start. There is also a chapter in Diestel's book which might be helpful to you.
In terms of your particular question, a quick google search found the following paper: "Extremal graphs of girth 5" by Garnick, Kwong and Lazebnik
