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

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?

share|cite|improve this question
See this… – Jernej Nov 11 '13 at 16:27
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.