Connected Components

Question

My Doubt is :- 

1. If n vertices are there and p are the connected components then total n-p edges will be there.

2. In a simple graph with n vertices and p connected components there are atmost (n-p)(n-p+1)/2  number of edges 

Now which to apply when Second one is given in Rosen.

Likewise:- 

1. Every connected graph has atleast n - 1 edges.

2. A simple graph with n vertices is connected if it has more then(i.e. atleast)  (n-1)(n-2)/2 edges.

Example:- A simple undirected graph ‘X’ has 10 vertices. If ‘X’ has 5 equally sized connected components, then, what is the maximum number of edges in graph ‘X’?

Now in this Question which one to apply ? Both will give different answer.

Well answer is 5 i used some example and by usual formula which we apply i.e. n-p it also gives 5 as the answer.

Solution of made easy:- (Please tell how did they approached the question and which way is the best way to do such questions)

Comments

1. A graph G with $n$ vertices and $k$ components has atleast $n-k$ edges.
2. A simple graph G with $n$ vertices and $k$ components has atmost $\frac{(n-k)(n-k+1)}{2}$ edges.

(First is for general graph and second is for simple graph, We can not talk about maximum number of edges in general graph. Notice that both theorems are applicable for simple graph. For below discussion lets stick to simple graph. )

Let a simple graph G with  $n$ vertices and $k$ components be $\color{blue}{(G,n,k)}$, then-

$ \boxed{ n-k \leq \text{No of edges in }  {(G,n,k)}  \leq \frac{(n-k)(n-k+1)}{2}}$

Try to grasp below intuition- 

• Why least $n-k$ edges ?,  Bcoz if you try for even less edges than $n-k$ then you cant have $k$ components, you will ended up having more than $k$ components.
•  Why most $\frac{(n-k)(n-k+1)}{2}$ edges ?,  Bcoz if you try for even more edges than $\frac{(n-k)(n-k+1)}{2}$ then  you cant have $k$ components, you will ended up having less than $k$ components.

Answer 1

You won't get confused if you know the proofs of all these theorems and how all these theorems are connected.

First of all, see that -

1. If a graph is connected then $e≥n−1$.
2. If a graph has more than $\frac{(n−1)(n−2)}{2}$ then it is connected.

Both the theorems are different.
Notice that the implications in 1 and 2 are in opposite directions.
The $1^{st}theorem$ says about how few edges can you use to connect all the vertices- (this is the case when your graph does not contain any cycle ) while $2^{nd}theorem$ says that you cannot construct an undirected disconnected graph with  $\frac{(n−1)(n−2)}{2}+1$ edges. 

---

        3.  A graph with n vertices and p connected components contains at least n-p edges.

Proof - 
Let $1^{st}$ component contains $n_1$ vertices, $2^{nd}$ component contains $n_2$ vertices ..   $p^{th}$ component contains $n_p$ vertices
Using theorem 1- $i^{th}$ component must contain a minimum of $n_i - 1$ edges to be connected.

So minimum number of edges in a graph $G$ with n vertices and p connected components $\Rightarrow$
$n_1-1+n_2-1+n_3-1+......n_p-1 $
 $\Rightarrow$ = {$\underset{n}{\underbrace{n_1+n_2+n_3....n_p}}- $($ \underset{P times}{\underbrace{1+1+1.....+1}}$)} 

 $\Rightarrow$ $n-p$

---

         4. In a simple graph with n vertices and p connected components, there are at most $\frac{(n-p)(n-p+1)}{2}$  number of edges -
Proof-
If you have a connected component with $x$ nodes in it, the maximum number of edges you can have in that connected component is $\frac{x(x - 1)}{2}$. Therefore, if you have $n$ total nodes and $p$ different connected components, you can imagine distributing the nodes into the connected components in a way that maximizes the sum of $\frac{x(x - 1)}{2}$  across the connected components.
This is maximized when $p - 1$ of the connected components have 1 node and the last connected component has $n - p + 1$ nodes in it.

So under this setup, the maximum number of possible edges in the $p - 1$ singleton Components will be 0 and the maximum number of possible edges in the last  Component will be $\frac{(n-p)(n-p+1)}{2}$ .

Therefore, In a simple graph with n vertices and p connected components, there is at most $\frac{(n-p)(n-p+1)}{2}$ edges%. 

---

        5. If each component contains an equal number of edges then the maximum number of edges that graph can have- 
$\frac{n(n - p)}{2p}$

Proof -
Let there are p connected components and each component contains x vertices- 
The maximum number of edges you can have in a single connected component is $\frac{x(x - 1)}{2}$.
So maximum number of edges that graph G contains $p*\frac{x(x - 1)}{2}$ .
$\frac{n(x - 1)}{2}$ .    $//px=n$
 Divide both numerator and denominator by p. We will get -
$\frac{n(n - p)}{2p}$

Now, Coming to your question- 

In the question n = 10 and p = 5
so $\frac{10(10 - 5)}{2*5} = 5$

Comments

well explained

---

A disconnected graph has at least 2 components.
Now take a graph with the maximum number of edges. This is the case of a complete graph.
A simple undirected graph with n vertices can have at most $\frac{n.(n-1)}{2}$ edges. 

Now disconnect the graph by disconnected one of its vertices(means remove all the edges that are incident on the n^th vertex).
The maximum number of edges between the remaining n−1 vertices can be  $\frac{(n-1).(n-2)}{2}$.
Now if u add 1 more edge to the graph it will again connect the n^th vertex.

You can prove in this way also -
A simple graph G with n vertices and k components have -
$n−k$ ≤ No of edges in G ≤ $\frac{(n−k)(n−k+1)}{2}$

Now put k=2. A simple graph G with n vertices and 2 components have -
$n−2$ ≤ No of edges in G ≤ $\frac{(n−2)(n−1)}{2}$

Now u doubt is how n-1 edges connect a graph.  ?
Put k=1. We need just 1 connected component. 
$n−1$ ≤ No of edges in G ≤ $\frac{(n)(n−1)}{2}$

Just draw some graphs. You will get it. This is the case of a tree.

In simple words, if u have $n-1$ vertices and no cycle then your graph if connected but if your graph contains cycle then n-1 edges can't connect that graph.
But if u have $\frac{(n-1).(n-2)}{2}+1$ edges no matter your graph contains a cycle or not. It will always be connected. 

---

@soumya 29 superb explanation

Answer 2

ALL three formula have diffrent meaning. we can take an example and try to understand it.