Lower bound on the order of the greatest connected component in a Graph

190 Views Asked by At

Theorem: Let $G$ be a graph of order $n$ ($n$ vertices) and size $e$ ($e$ edges), with $n > 1$. $G$ consists of $r$ connected components ($r > 0$), each of order $l_i$. If $L$ is the order of the largest (in term of vertices) connected component, then $$e/n \leq (L - 1)/2$$

Now, if we reformulate the last expression as $2e/n \leq (L - 1)$, we are just saying that the expected (average) value of the degree of a vertex in $G$ (which is $2e/n$) is less or equal than (L - 1). But this is clear since if we let $D$ being the maximum degree of vertices of $G$, then we must have $$D\leq(L-1)$$

By the Pigeonhole principle of Expectation, $\mathrm{Expected(vertex degree)}<= \mathrm{max(vertex degree)}<=(L - 1)$, which proves the theorem.

Now, is there a more "algebraic" way of showing the above, in particular using that: $$\sum_{i=1}^{r} l_i = n$$ and also $$\sum_{i=1}^{r}{l_i\choose2}\geq e$$

1

There are 1 best solutions below

1
On BEST ANSWER

Sure: we have $$ e \le \sum_{i=1}^r \binom{l_i}{2} = \sum_{i=1}^r \frac{l_i(l_i-1)}{2} \le \sum_{i=1}^r \frac{l_i(L-1)}{2} = \frac{L-1}{2}\sum_{i=1}^r l_i = \frac{L-1}{2}\cdot n, $$ from which $$ \frac en \le \frac{L-1}{2}. $$