# If $|V(G)|=n$ and $e(G)>\frac{n}{4}\{1+\sqrt{4n-3}\}$ then $G$ contains 4-cycle

This question is linked to my former question Special properties of subgraphs

I want to practice this technique a little bit more and want to show that if $|V(G)|=n$ and $e(G)>\frac{n}{4}\{1+\sqrt{4n-3}\}$ then $G$ contains 4-cycle. I want to prove it by induction and start in a similar as mentioned in the former question:

First check it for $n=4$, this is the trivial case (Besides I assume $n\ge 4$)

Now I go from $n-1\rightarrow n$ The average number degree number of an arbitrary vertex is $\frac{2e(G)}{n}>\frac{1}{2}\{1+\sqrt{4n-3}\}$. Therefore $\exists v\in V(G): d(v)\le \frac{1}{2}\{1+\sqrt{4n-3}\}$. I take a new graph $G'=G-v$ with $e'(G)=e(G)-d(v)$. I want to show that $e'(G)\ge\frac{n-1}{4}\{1+\sqrt{4(n-1)-3}\}$

First I check the LHS: $e'(G)=e(G)-d(v)\ge e(G)-\frac{2e(G)}{n}=e(G)\frac{n-2}{n}>\frac{n-2}{4}\{1+\sqrt{4n-3}\}$

Therefore it remains to show $\frac{n-2}{4}\{1+\sqrt{4n-3}\}>\frac{n-1}{4}\{1+\sqrt{4(n-1)-3}\}$ but how I can prove this?

-
See this exwiki.org/mw/… –  Jernej Nov 11 '13 at 16:27

## 1 Answer

Direct manipulation until you have something of the form $a\sqrt{b}>c+d\sqrt{e}$. Now square. You have only one term with a square root left. Move all other terms to the other side and square again. You are left with a polynomial in $n$ of degree at most 6 that should be easy to analyze.

-