Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 1

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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