retagged by
11,418 views
51 votes
51 votes
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
retagged by

4 Answers

Best answer
63 votes
63 votes

$N$ vertices and  $K$ components.
(Component means they are non connected subgraphs)

We want maximum edges in total graph. How to get maximum edges ?

To get maximum,  take one vertex each for each component,  except last component.
Now $k-1$ components have $1$ vertex each and so no edges.
The last component has  $n-(k-1)$ vertices.
So make the last component complete.
i.e., It has ${}^{n-(k-1)}  C_ 2 =\frac{ (n-k) (n-k+1) }{ 2}$  edges.  

Must do a similar model qsn on forest:   https://gateoverflow.in/580/gate1992_03-iii

selected by
45 votes
45 votes

Hopefully it should be clear that in any such graph all components will be complete, i.e., have all possible edges. Thus the only remaining question is how large each component should be?

If there are two components with $a$ and $b$ vertices, $a>1, b> 1$, then together they can have at most

$\binom{a}{2} + \binom{b}{2} = \frac{1}{2} \left(a^2 - a + b^2 - b \right)$ edges.

However, if we place all but one of the vertices in a single component, we could have

$\binom{a+b-1}{2} + \binom{1}{2} = \frac{1}{2} \left(a+b-1\right)\left(a + b - 2\right)$
$=\frac{1}{2} \left(a^2 + 2ab -3a + b^2 - 3b + 2 \right)$ edges.

Subtracting the first quantity from the second gives

$\frac{1}{2}\left(\left(2ab - 3a - 3b +2\right) - \left(-a - b \right)\right) \\=ab-a-b+a \\= (a-1)(b-1) \text{ which is } > 0$

Hence it is better not to have two components with multiple vertices.

This leaves us with the answer that all components should have one vertex except one, which will have $n-k+1$  vertices, for a total of $\binom{n-k+1}{2}$ edges.

In simple connected graph, with number of edges as $e,$ we have

$(n-1) \leq e \leq n. \frac{(n-1)}{2}$

In simple disconnected graph with $k$ components and number of edges as $e,$ we have

$(n-k) \leq e \leq (n-k).\frac{(n-k+1)}{2 }$

Note: Put $k=1$ then it will be connected graph .

Reference @ http://www.quora.com/What-is-the-maximum-number-of-edges-in-graph-with-n-vertices-and-k-components
Another read @ http://stackoverflow.com/questions/24003861/maximum-number-of-edges-in-undirected-graph-with-n-vertices-with-k-connected-com

edited by
43 votes
43 votes
easy one.
if u want maximum number of nodes and k vertices then u should have k-1 components. with only one vertices and only one should contain remaining vertex ,

like

if i take 6 vertex and have to make 4 component then i will make the  4 component in this way ,

1 vertex 1 vertex 1 vertex 3 vertex.

and now i will make the last one complete graph . then it will have maximum number of edges.

so if u have n vertices and k component then just give (k-1) component one vertex and the remaining will be (n-(k-1)) now make that bigger one a complete graph . i.e ( n-k+1) ( n-k-1+1)/2 complete graph formula . n(n-1)/2 = (n-k)(n-k+1)/2
edited by
0 votes
0 votes

when graph do not contain self loops and is undirected then the maximum no. of edges are-

(n-k+1)(n-k)/2

It is because maximum number of edges with n vertices is n(n-1)/2.


Now for example, if we are making an undirected graph with n=2 (4 vertices) and there are 2 connected components i.e, k=2, then first connected component contains either 3 vertices or 2 vertices, for simplicity we take 3 vertices (Because connected component containing 2 vertices each will not results in maximum number of edges). These 3 vertices must be connected so maximum number of edges between these 3 vertices are 3 i.e, (1->2->3->1) and the second connected component contains only 1 vertex which has no edge. So the maximum number of edges in this case are 3. This implies that replacing n with n-k+1 in the formula for maximum number of edges i.e, n(n-1)/2 will results in (n-k+1)(n-k)/2 which is maximum number of edges that a graph of n vertices with k connected component can have.

Related questions

19 votes
19 votes
3 answers
1
Kathleen asked Sep 12, 2014
5,671 views
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
16 votes
16 votes
1 answer
2
Kathleen asked Sep 12, 2014
3,133 views
A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ______
37 votes
37 votes
1 answer
3
Kathleen asked Sep 12, 2014
4,777 views
When two $4$-bit numbers $A = a_3a_2a_1a_0$ and $B=b_3b_2b_1b_0$ are multiplied, the bit $c_1$ of the product $C$ is given by ________
24 votes
24 votes
3 answers
4
Kathleen asked Sep 12, 2014
4,357 views
Consider the following PASCAL program segment:if i mod 2 = 0 then while i >= 0 do begin i := i div 2; if i mod 2 < 0 then i := i - 1; else i := i – 2; end;An appropria...