The Gateway to Computer Science Excellence

+2 votes

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

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 vote

Best answer

52,217 questions

59,951 answers

201,132 comments

118,173 users