# Small cycles in an undirected graph

Let $G=(V,E)$ be an undirected graph. I am using the usual convention that $n=|V|, m=|E|$. For $v \in V$, let $deg(v)$ be the degree of the vertex $v$.

I am trying to show that if we have $m > \frac{n^{3/2}}{2}$, it follows that $G$ has either a triangle $C_3$ or a square $C_4$. I found a neat way that almost works, but it is not tight enough...

Here is what I have done so far:

First of all (not concerning the solution but a related problem) it is a neat example of the Cauchy-Riemann inequality to show that every graph $G$ with more than $n^2/4$ edges contains a triangle $C_3$ (this is Mantel's theorem).

Now I did this (basically I reproduce a proof given by Erdős):

I try to show if $G$ has no square $C_4$, then $m \leq \frac{n^{3/2}}{2}$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a "cherry"). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:

$$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Now if we don't allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore

$$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Then due to convexity of $\binom{x}{2}$ and the Jensen Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4 n-3)}+n\right)$. Sadly after all the work I see that asymtotically this is enough but the bound I want to show is still a big tighter:

I would be very glad if someone could give me an alternate proof that gives me the tight bounds or maybe refine what I did (I did not use the fact yet that $G$ is also triangle-free).

-

## 1 Answer

A proof can be found in:

Garnick, David K., Kwong, Y. H. Harris, Lazebnik, Felix, Extremal graphs without three-cycles or four-cycles. J. Graph Theory 17 (1993), no. 5, 633–645.

-

You are right, thank you! I will try to understand the proof when I am back home, how did you find this :-)? I basically searched for hours and came up with nothing. – Listing Oct 23 '11 at 11:23
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9508063793182373, "perplexity_flag": "head"}