2,379 views
5 votes
5 votes
Stmt 1: A simple graph is necessarily connected if |E| > (n-1)*(n-2)/2.

Stmt2: A simple graph with n vertices and k components has at least n-k edges.

Can you please explain how are these results derived?

2 Answers

Best answer
7 votes
7 votes

Statement 1 :-  A simple graph is necessarily connected if |E| > $\frac{(n-1)(n-2)}{2}$

( Proof already given by Rishav Kumar Singh, credit goes to him )

Let we have n vertices in a graph.

If we put  1 vertex aside we have n-1 vertices.

with n-1 vertices max edges we could have when graph is complete is (n-1)C2 which is $\frac{(n-1)(n-2)}{2}$.

We can see that with $\frac{(n-1)(n-2)}{2}$ much edges we have one vertex left aside which makes graph disconnected.

So to connect that vertex we need one more edge. So total number of edges > $\frac{(n-1)(n-2)}{2}$

 

Statement 2:-  A simple graph with n vertices and k components has at least n-k edges.

let take in each component we have ni vertices ===> n1 in 1st component, n2 in 2nd component.... nk in kth component

∴ n1+n2+....+nk = n

note that minimum edges occurs in a tree ( if the tree has P vertices then it contains P-1 edges ) ==> Assume each component is Tree

The 1st component contains vertices ===> it contains ( n1 -1 ) edges

The 2nd component contains vertices ===> it contains ( n2 -1 ) edges

.....

The kth component contains vertices ===> it contains ( nk -1 ) edges

total edges = edges in 1st component + edges in 2nd component + .......+ edges in kth component

                 = ( n1 -1 ) + ( n2 -1 ) + .........+ ( nk -1 )

                 = ( n1 + n2 + .........+  nk  ) - ( 1+1+1+....k times)

                 = n - k

these no.of edges atleast possible in the graph which have k components ( if any component is not tree then no.of edges should be increase. )

selected by
0 votes
0 votes
You can think like this . if we have a graph with n vertices then to show that graph is connected we can say that it has minimum n-1 edges but keep in mind this does not guarantee that with n-1 edges this graph will always be connected. These n-1 edges can be joined anywhere.

However if you take n-1 vertices and leave one vertex , then maximum number of edges will be C(n-1,2) which is (n-1)(n-2)/2  and last vertex you can join with one edge , now it will be guaranteed that graph will be connected.

for statement 2 :

if there are k components let just say each having n1,n2,...nk where n1+n2+n3...nk=n then for each component min vertex will be n1-1, n2-1,n3-1… if you sum them $\sum$ ni-i where i varies from 1 to k  which will be n1+n2+n3...nk +1+1+1...ktimes which will be n-k

Related questions

2 votes
2 votes
2 answers
1
rahul sharma 5 asked Jun 12, 2017
1,984 views
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
0 votes
0 votes
0 answers
2
3 votes
3 votes
0 answers
3