Ace Test Series: Graph Theory - Graph Connectivity

Question

Comments

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.

Answer 1

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  

Comments

Thanks aehkn and Prabhanjan_1 for the help.