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.

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|improve this question
    
See this exwiki.org/mw/… –  Jernej Nov 11 '13 at 16:27
add comment

1 Answer 1

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|improve this answer
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.