The Gateway to Computer Science Excellence

+40 votes

The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.

+41 votes

Best answer

$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*

0

nice way. it is easy to visualize by taking example like if we take 6 vertex and 2 componenet. there r multiple way to draw the graph like (1,5) (2,4) (3,3)... so on in braket 1st no. shows vertex in first component like this if we draw this we see that maximum condition occurs only when all componets have 1 vertex and 1 component have all remaining vertices.

+34 votes

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 , number of edges ,

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

in simple unconnected graph with k component , number of edges ,

$(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

+31 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

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

52,345 questions

60,497 answers

201,858 comments

95,314 users