1
$\begingroup$

I know that in a Graph $G$ Containing $n$ vertices and $k$ edges,$G$ will contain atleast $n-k$ components.

Explanation-:

Graph containing $n$ vertices and $0$ edges will contain $n$ components.Each time adding an edge will reduce the component by 1.Thus $k$ edge will contain $n-k$ component. This is the minimum number.

I am interested in finding the maximum number of component.please help me out !!!

$\endgroup$
  • $\begingroup$ By the way, this question considers only simple graphs, right? $\endgroup$ – rgm Dec 30 '16 at 15:37
  • $\begingroup$ @shn yes it is simple graph ! $\endgroup$ – virat Dec 30 '16 at 16:30
1
$\begingroup$

In the worst case the edges are used to form a clique. Let $i$ be the smallest integer $\ge 1$ s.t. $\frac{i(i-1)}{2} \ge k$. There are $n-i+1$ connected components in that case, which is maximal posible.

$\endgroup$
  • $\begingroup$ Just beat me to it. +1 $\endgroup$ – AlgorithmsX Dec 27 '16 at 20:20
1
$\begingroup$

The maximum number of components comes from using complete graphs. For instance, with two edges, you lose two components. With three edges, you can make a complete subgraph and lose no edges. The result is $n-l$ such that $l$ is the lowest integer satisfying $k\le \frac{l(l+1)}2$, where $k$ is the number of edges, $n$ is the number of nodes.

$\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.