# graph avoiding cycle of length 4

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

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

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.

-
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