328 views
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?
| 328 views
+4
Statement 1

Let we have n vertices in a graph. If we put  1 vertex aside we have n-1 vertices so, with n-1 vertices max edges we could have when graph is complete is (n-1)C2 which is (n-1)(n-2)/2. We can see that with (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 > (n-1)*(n-2)/2.
+4
This is not a formal proof but you can visualise what's going on.

Statement 2

Let we have n vertices and n components. it means graph has no edge. Let's add an edge between two vertices then component going to be decrease by 1. Here we can see, edge = n-k.

But graph is still disconnected, to make this graph connected minimum number of edges we need is n-1 which makes it a tree. now graph is connected and has only one component. So  edges = n-k=n-1.
+1

@Rishav Kumar Singh

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. )

by Veteran
selected