The Gateway to Computer Science Excellence
+2 votes

in Graph Theory by Loyal
edited by | 203 views
Please explain above formula for number of edges
wkt max no.of edges  in a complete graph = nC2

Consider a case where keep n-1 vertices on one side and 1 vertex on other side .

Now maximum no of edges in the first one is n-1C2

Still the graph is disconnected.

adding edge to vertex 1 makes graph connected.

So (n-1) (n-2) / 2  + 1  => 172

Let G be a graph with n vertices and if every vertex has a degree of at least $\lfloor \frac {n}{2} \rfloor$ then G is connected.
Degree of each vertex = 20/2 = 10. Total degree = 10*20 = 200. Number of edges = 200/2 =100
Where am I wrong? Please explain


Consider two cases here

1) To make it simple , we take a 5 vertex graph,

Consider your approach ....

Now each vertex must be having atleast a degree of 2.

So total number of edges i get are = 6edges.

2) Consider the above approach 

Now one side is fully connected => gives 6 edges 

adding one edge makes it  to connect entire graph = > 7 edges.

BUT ,Consider (1) ,, i can show a graph with 6 edges and  is not connected .(connecting everything on one side)

but one cannot show a graph with 7 edges and not connected.

1 Answer

+1 vote
Best answer

Here they are asking Necessary condition which will ensure graph will connected in any case 
Also e should be strictly greater than (n-1)(n-2)/2  

by Active
selected by

Thanks aehkn and Prabhanjan_1 for the help. 

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
52,217 questions
59,951 answers
118,173 users