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!


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.

  • $\begingroup$ Füredi's paper, with its connection to finite projective planes, was a pleasant surprise for me. In particular I recognized several of his literature citations as ones I'd come across in connection with this Question. $\endgroup$ – hardmath Nov 19 '13 at 15:34
  • $\begingroup$ According to the paper for quadrilateral-free graph of size $n$, the maximum number of edges is $O(n^\frac{3}{2})$. The co-efficient $\endgroup$ – Vivek Bagaria Apr 29 '14 at 5:40
  • $\begingroup$ Are there any such results for graphs whose girth is strictly greater than $5$ $\endgroup$ – Vivek Bagaria Apr 30 '14 at 9:38
  • $\begingroup$ @Bagaria: I'll take a look, but it seems like a harder problem. It would make a good Question to post separately. $\endgroup$ – hardmath Apr 30 '14 at 11:41
  • $\begingroup$ @Bagaria: You'll probably find this MathOverflow post, Largest graphs of girth at least 6, of interest. It tabulates the maximum size (number of edges) for given order (number of vertices), though it cautions the values are not well checked, and the Question is about whether a bipartite graph exists that attains the maximum number. $\endgroup$ – hardmath May 1 '14 at 12:49

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

  • 2
    $\begingroup$ Also, Füredi, Z.: On the number of edges of quadrilateral-free graphs. J. Comb. Theory Ser. B 68(1), 1–6 (1996) $\endgroup$ – hardmath Nov 18 '13 at 13:53
  • $\begingroup$ @Casteels: In the introduction section of the paper "Extremal Graphs of Girth Five", the answer seems to be asymptotically ~ *n^{3/2}. Am I missing something? $\endgroup$ – Vivek Bagaria Nov 18 '13 at 14:08
  • $\begingroup$ Yeah looks like it. $\endgroup$ – Casteels Nov 18 '13 at 14:24
  • 1
    $\begingroup$ Note that "girth 5" implies $C_3$-free as well as $C_4$-free. $\endgroup$ – hardmath Nov 19 '13 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.