Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Posting questions in the imperative like this is generally considered impolite. Please refer to… . – 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: for a discussion of these ideas. – Joseph Malkevitch Dec 8 '11 at 20:49
up vote 3 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|cite|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

Your Answer


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.