Doubt:

Question

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?

Answer 1

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

Comments

This question answered several times in GO. My suggestion is, don't waste your time to write answers for which answers already exists. Just search for duplicates before you want to write answers.