0
$\begingroup$

A graph with $n$ vertices and $p$ components has at least $n-p$ edges. Can I give an upper bound for the number of edges of such a graph? If so, how to prove it?

My attempt:

For each component, we have that the number of edges $m_i$ is given by $m_i \le \binom{n_i}{2}$, with $n_i$ the number of vertices within a component. So $m \le \sum_{i=1}^p \binom{n_i}{2} \le p\binom{n}{2}$.

Thanks.

$\endgroup$
2
$\begingroup$

The maximum occurs when $p-1$ of the components are singletons, so the number of edges is $\binom{n-p+1}{2}$.

Proof: Since the problem is finite, it suffices to show the maximum doesn't lie elsewhere. We may assume WLOG each component is a complete graph. If the maximum occurs with at least 2 nontrivial components, then move one vertex from the smaller (if equal just pick one) to the larger would increase the number of edges, contradiction. QED.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.