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$ be a simple graph on $n$ vertices such that $G$ has no cycle of length $4$. show that $e(G)\le \frac{n}{4}(1+\sqrt{4n-3})$ where $e(G)$ denotes the number of the edges of the graph $G$.

share|improve this question
1  
Posting questions in the imperative like this is generally considered impolite. Please refer to meta.math.stackexchange.com/questions/1803/… . –  Brad Dec 8 '11 at 16:41
1  
It might be of interest for you to think about graphs which have cycles of all lengths (pancyclic) graphs as well as those which are missing a cycle of exactly one length (almost pancyclic) - see: en.wikipedia.org/wiki/Pancyclic_graph for a discussion of these ideas. –  Joseph Malkevitch Dec 8 '11 at 20:49
add comment

1 Answer

up vote 2 down vote accepted

I included a proof of what you want in a question of mine where I asked for a tighter bound if the graph avoids also cycles of length 3: (I use the convention $m:=e(G)$)

I try to show if $G$ has no subgraph $C_4$, then $m \leq \frac{n}{4}(1+\sqrt{4n-3})$. 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 (4n-3)}+n\right) $.

This is a link to Jensen's inequality in case you don't know it.

Edit: As the operator asked for more details:

Define $\varphi(x):=\binom{n}{2}$, it is easy to see that $\varphi$ is convex. Therefore we have that

$$\varphi\left(\frac{\sum x_i}{n}\right) \le \frac{\sum \varphi (x_i)}{n} \iff \sum \varphi (x_i) \geq n\cdot \varphi\left(\frac{\sum x_i}{n}\right)$$

And therefore

$$\binom{n}{2} \geq \sum_{v\in V}\binom{\text{deg}(v)}{2} \geq n\cdot \binom{\frac{1}{n}\sum_{v\in V}\text{deg}(v)}{2}=n\cdot\binom{\frac{2m}{n}}{2}$$

Because the sum over all degrees of the nodes corresponds to twice the amount of edges. Expanding the binomial on both sides yields your result.

share|improve this answer
    
I know Jensen's function, but would you please show me how to apply it here? every time I use it on this question I get $m\le \frac{n}{4}(1+2\sqrt{n})$. –  Goodarz Mehr Dec 8 '11 at 17:18
    
@goodarzmehr I tried to be a bit more explicit. I hope you understand it now. –  Listing Dec 8 '11 at 17:36
    
now I undrestand, thanks a lot :) –  Goodarz Mehr Dec 9 '11 at 18:39
    
no problem :P, good that you understood it –  Listing Dec 9 '11 at 19:58
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.