The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
193 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?
in Mathematical Logic by (197 points) | 193 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

formal proof added as answer for statement 2

1 Answer

+6 votes
Best answer

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 (63.4k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,358 comments
90,818 users