Intereting Posts

Difference of closures and closure of difference
What is the integral of $e^{a \cdot x+b \cdot y}$ evaluated over the Koch Curve
A pencil approach to find $\sum \limits_{i=1}^{69} \sqrt{\left( 1+\frac{1}{i^2}+\frac{1}{(i+1)^2}\right)}$
How do you calculate this limit $\mathop {\lim }\limits_{x \to 0} \frac{{\sin (\sin x)}}{x}$?
coin toss question
Isometry in $\mathbb{R}^n$
Infinite prisoners with hats — is choice really needed?
Why is the tensor product important when we already have direct and semidirect products?
Finding the elements of a finite field?
Algorithm(s) for computing an elementary symmetric polynomial
Cutting the Cake Problem
Ratio test and the Root test
Understanding the definition of the Riemann Integral
On the mean value of a multiplicative function: Prove that $\sum\limits_{n\leq x} \frac{n}{\phi(n)} =O(x) $
proving that $\frac{(n^2)!}{(n!)^n}$ is an integer

**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$)?

- How can we show that 3-dimensional matching $\le_p$ exact cover?
- $\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof
- combinatorics olympiad problem - sort out a schedule
- How many ways to place n distingusishable balls into m distinguishable bins of size s?
- Derivation of the Partial Derangement (Rencontres numbers) formula
- Truncated alternating binomial sum

**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!

- How many 4 digit numbers can be made with exactly 2 different digits
- Proof a graph is bipartite if and only if it contains no odd cycles
- counting full bipartite matchings
- Software to find out adjacency matrix of a graph.
- A set of integers whose elements all divide $2015^{200}$ but do not divide each other
- upper bounding alternating binomial sums
- Combinatorial argument for $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$
- 2 color theorem
- Round-robin party presents (or: Graeco-Latin square with additional cycle property)
- At least one monochromatic triangle from $p_n=\lfloor{en!}\rfloor+1$ points

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

- Example where closure of $A+B$ is different from sum of closures of $A$ and $B$
- Topological space definition in terms of open-sets
- How can this integral expression for the difference between two $\zeta(s)$s be explained?
- ArcTan(2) a rational multiple of $\pi$?
- The group of invertible fractional ideals of a Noetherian domain of dimension 1
- computing the series $\sum_{n=1}^\infty \frac{1}{n^2 2^n}$
- Discontinuity of Dirac Delta distribution
- Points of discontinuity of a bijective function $f:\mathbb{R} \to [0,\infty)$
- Singular-value inequalities
- Is there a name for the group of complex matrices with unimodular determinant?
- Do there exist Artificial Squares?
- Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?
- Which Lie groups have Lie algebras admitting an Ad-invariant inner product?
- $\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$
- Hölder continuous but not differentiable function