3
$\begingroup$

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

2 Answers 2

4

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.

3

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.

  • 0
    I was halfway through writing when you answered this. Since our methods are identical I have to +1 this.2012-11-30