Take the 2-minute tour ×

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:

enter image description here

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).

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
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
add comment

Your Answer


