The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
174 views

in Graph Theory by Loyal (8.8k points)
edited by | 174 views
0
Please explain above formula for number of edges
0
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
0

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

0

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

Thanks aehkn and Prabhanjan_1 for the help. 

Related questions

0 votes
1 answer
4
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,362 questions
55,788 answers
192,413 comments
90,927 users