in Graph Theory retagged by
7,639 views
46 votes
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
in Graph Theory retagged by
7.6k views

1 comment

I first saw Tendua’s explanation(Scroll down) then only the proofs made sense. thanks.
1

Subscribe to GO Classes for GATE CSE 2022

3 Answers

50 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

selected by
by

4 Comments

Nice .... (y)
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.
0
edited by
Component of a GRAPH – Subgraph.

Component of a FOREST – Tree.

These two definitions are the keys to solving this question and the question mentioned in the link.
2
Good
0
39 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

9 Comments

cool...
0

Very Well Explained .

0

Please refer to my query.

0
edited by

As this formula is derived for maximum number of edges you can refer this

6
wat is 1C2 in calculation ??
0

Swati Rauniyar  keep 2 vertices isolated and make a complete graph of remaining 5 vertices

0
nice explanation @mithlesh
0
Your comment saved me. Thank you saumya mishra :)
0
Excellent answer.

This is a better answer with a little bit flavor of the proof.
0
37 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

2 Comments

Please resolve my query.

0
Here, they have asked maximum number of edges. The number of edge in any graph with n vertices and k components lies between   n-k and (n-k+1)(n-k)/2. We have to keep the number of vertices in each component such that the total number of edges is maximum.
0

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true