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!

Solutions Collecting From Web of "Maximum edges in a square free graph"

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.

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