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!

Solution 1:

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.

Solution 2:

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