edited by
630 views
0 votes
0 votes
Let “m” be the number of edges, “n” the number of vertices and “k” the number of connected components of a graph G.

Prove that:

$\left ( n-k \right )\leq m\leq \frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$

Why least number of edges are $\left ( n-k \right )$ and Why most number of edges are $\frac{\left ( n-k \right )\left ( n-k+1 \right )}{2}$ ? What is the idea behind this prove?
edited by

1 Answer

2 votes
2 votes

So starting with minimum number of edges.

Given ,

Number of edges =$m$

Number of vertices=$n$

Number of Component=$k$

Now say each component $G_{1},G_{2},G_{3},.....G_{k}$ has  $n_{1},n_{2},n_{3},.....n_{k}$ vertices respectively.

So , $n_{1}+n_{2}+n_{3}+....+n_{k}=n$

 each component is a connected graph. So, we have $k$ such connected graph as it is given we have k connected component.

Now consider Component $G_{1}$, which has $n_{1}$ vertices.

So we know it already minimum number edge in a undirected connected graph is $n-1$ . So for Component $G_{1}$ minimum number of edge is $n_{1}-1$.

For component $G_{2}$ ,minimum number edge is $n_{2}-1$.

So on,

For component $G_{k}$ minimum number edge is $n_{k}-1$.

So , Total number of edges in the graph 

=$(n_{1}-1)+(n_{2}-1)+(n_{3}-1)+.......+(n_{k}-1)$

=$n_{1}+n_{2}+n_{3}+.......+n_{k}-k$

=$n-k$


For the second case , We get maximum number of edges only when we have one big component with n-k+1 vertices with edges  and rest k-1 component with 1 vertices with no edges .

The component with n-k+1 vertices should form a complete graph to make maximum number of edges.

So , Number of edges in a complete graph with (n-k+1) vertices is,

$\binom{n-k+1}{2}$=$\frac{(n-k)(n-k+1)}{2}$

Proof for this can be deduce by contradiction .

Link :- https://math.stackexchange.com/questions/1075692/number-of-edges-in-a-graph-with-n-vertices-and-k-connected-components

Related questions

0 votes
0 votes
2 answers
1
raja11sep asked Jan 5, 2022
495 views
Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?
0 votes
0 votes
1 answer
2
Cristine asked Jan 27, 2019
2,640 views
what is the diameter and radius of the complete bipartite graph?
0 votes
0 votes
0 answers
3