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.

I'm working on proving that if a simple graph with $n$ vertices has more than $5n^2/18$ edges then the graph has no connected component of size between $n/3$ and $2n/3$.

Logically, I think I could show it but I'm not sure how to prove it.

Thanks

share|improve this question
add comment

2 Answers

Lemma: Let $G$ be a graph on $n$ vertices with more than $\frac{5n^2}{18}$ edges. If $G$ has a connected component $C$ of size between $\frac{n}{3}$ and $\frac{2n}{3}$ then there exists a graph $G'$ which satisfies the same hypothesis with exactly two connected components.

Proof: Clearly the component $C$ in question cannot be the whole graph $G$. If $G$ has exactly two components, then we are done. Otherwise, connect all components other than $C$ together by introducing arbitrary edges. The resulting graph is on $n$ vertices, with more than $\frac{5n^2}{18}$ edges and with exactly $2$ connected components, one of which is of size between $\frac{n}{3}$ and $\frac{2n}{3}$. $\square$

Now let us take a look at the maximum amount of edges a graph with two connected components can have. Let $m$ be the order of one component and $n-m$ the order of the other. Then the maximum amount of edges is clearly $$\binom{n-m}{2} + \binom{m}{2} = \frac{(n-m)(n-m-1)}{2} + \frac{m(m-1)}{2}$$ We require this quantitity to be greater than $\frac{5n^2}{18}$. This gives the following inequality $$18m^2 - 18nm + 4n^2 -9n > 0$$ We solve this as a quadratic in $m$. From the quadratic equation, the roots occur at $$\frac{18n \pm \sqrt{(18n)^2 - 4(18)(4n^2 - 9n)}}{36}=\frac{2n \pm \sqrt{n^2 + 18n}}{6}$$ We therefore require $$m < \frac{n}{2} - \frac{\sqrt{n^2 + 18n}}{6} \le \frac{n}{2} - \frac{n}{6} = \frac{n}{3}$$ as a lower bound and $$m > \frac{n}{2} + \frac{\sqrt{n^2 + 18n}}{6} \ge \frac{n}{2} + \frac{n}{6} = \frac{2n}{3}$$ as an upper bound. In fact, since $\sqrt{n^2 + 18n} \sim n$ these bounds are tight.

Therefore there cannot exist a graph satisfying the hypothesis on $2$ components and hence there cannot exist such a graph on any number of components by the first lemma.

share|improve this answer
add comment

So, given a graph with one subgraph of $k$ vertices disconnected from the rest of the graph (the subgraph might be connected, might not). What is the maximum number of edges possible in a graph like that? That would be the sum of edges in the total graph of $k$ vertices and the total graph of $(n-k)$ vertices. That gives an upper bound for the number of edges (there might be arithmetic errors in here, it was hastily put together):

$$ \frac{k^2 - k}{2} + \frac{(n-k-1)(n-k)}{2} = \frac{n^2 - n}{2} - k(n-k) $$ We want to se what happens if we demand that the number of edges is higher than $5n^2/18$, so we solve this inequality with respect to $k$: $$ \frac{n^2 - n}{2} - k(n-k) > \frac{5n^2}{18} $$ I reduce the corresponding equality to $$ k = \frac{n}{2}\pm\frac{\sqrt{n^2 + 18n}}{6} $$ with solutions outside the interval $[\frac{n}{3},\frac{2n}{3}]$, so if $k$ is within the interval the inequality cannot hold.

share|improve this answer
    
I was halfway through writing when you answered this. Since our methods are identical I have to +1 this. –  EuYu Nov 30 '12 at 20:14
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.