<p>According to the following paper by <a href="http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_C4abs.ps" rel="nofollow">Füredi</a>, the maximum number of edges for a graph with $n$ vertices is upper bounded by $O(n^{\frac{3}{2}})$, where the leading co-efficient of the term $n^{\frac{3}{2}}$ is $\frac{1}{2}$. The paper also provides examples of graphs, for certain special values of $n$, where the number of edges exactly equal to the upper bound. </p>

<p>I wanted to know there exists graphs G(V,E) ($|V| = n $) for all values of $n$ such that</p>

<p>$$\Big|E - \small{\frac{1}{2}}n^{\frac{3}{2}}\Big| = o\big(n^\frac{3}{2}\big)$$</p>

CC BY-SA 3.0
2014-04-29T11:55:27.927Z
What you want follows from the result of Füredi that you mentioned and the known bounds on gaps between primes (e.g. those of Baker-Harman-Pintz).
Boris Bukh
CC BY-SA 3.0
2014-05-29T01:39:22.120Z
@BorisBukh comment -> answer?
Sasho Nikolov
CC BY-SA 3.0
2014-05-29T18:38:10.477Z
No. It is not a research-level question.
Boris Bukh
<reference-request><graph-theory><co.combinatorics>
Edges in a graph with girth greater than 4
Vivek Bagaria
# Edges in a graph with girth greater than 4

(Asked by: username_0 on 2014-04-29)

According to the following paper by [Füredi](http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_C4abs.ps), the maximum number of edges for a graph with $n$ vertices is upper bounded by $O(n^{\frac{3}{2}})$, where the leading co-efficient of the term $n^{\frac{3}{2}}$ is $\frac{1}{2}$. The paper also provides examples of graphs, for certain special values of $n$, where the number of edges exactly equal to the upper bound.

I wanted to know there exists graphs G(V,E) ($|V| = n $) for all values of $n$ such that

$$\Big|E - \small{\frac{1}{2}}n^{\frac{3}{2}}\Big| = o\big(n^\frac{3}{2}\big)$$

**Tags:** reference-request, graph-theory, co.combinatorics
> **Comments:**
> **username_1**: What you want follows from the result of Füredi that you mentioned and the known bounds on gaps between primes (e.g. those of Baker-Harman-Pintz).  
> **username_2**: @BorisBukh comment -> answer?  
> **username_1**: No. It is not a research-level question.  

---

## 0 answers

