combinatoricsgraph theoryreference-request
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!
Solved it!
Let G be a triangle-free graph on 5 vertices, and let E be the number of edges in G.
For every set of three distinct vertices $\{a,b,c\}$, count the number of edges connecting pairs of $a,b,c$. This number is at most 2 for each choice of $\{a,b,c\}$, since G is triangle-free. Thus, if we add this number over all choices of $\{a,b,c\}$, we get at most $\binom 53\cdot 2 = 20$. The sum obtained in this way is 3E, because every edge $a\text{---}b$ is counted as part of three triples. Therefore, $3E\le 20$, which sets an upper bound of $E=6$.
We can realize $E=6$ in the following triangle-free graph:
![1]](https://latex.artofproblemsolving.com/3/7/e/37e5874ca1da264a885e6af8eb5414e482304926.png)
Notice that all edges extend from a vertex in the left column to a vertex in the right column. This gives clear proof that the graph is triangle-free, since any cycle must be of even length.
We have proved that $E\le 6$ and that we can achieve $E=6$. Therefore, the maximum achievable value of E is exactly $\boxed 6$.
Apparently, we still need to prove that there cannot be $17$ edges or more under the given conditions. In fact, if our graph has at least $17$ edges, then removal of two vertices of degree $3$ will lead to removal of no more than $6$ edges. But then we would get a graph with $5$ vertices and at least $11$ edges, which is impossible.
Graph $K_{3,4}$ has $12$ edges and $4$ vertices of degree $3$. If a graph has $7$ vertices and $13$ edges, then it cannot be bipartite. This can be easily checked because graphs $K_{1,6}$ and $K_{2,5}$ have $6$ and $10$ edges respectively and it is obvious that any bipartite graph is complemented to a complete bipartite graph with the same number of vertices.
Best Answer
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.