# Proving component size based on number of edges and vertices.

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

-

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.

-

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.

-
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