611 views
3 votes
3 votes

Let A has n vertices. If Ā is connected graph then the maximum number of edges that A can have is

a) (n-1)(n-2)/2
b) n(n-1)/2
c) n-1
d) n

2 Answers

Best answer
3 votes
3 votes
If  $A^c$   is connected then minimum no. of  edges in $A^c$   are n-1

so  maximum no. of edges in A= Total edges - minimum edges in $A^c$

= $_{2}^{n}\textrm{c}$ - (n-1)

=n(n-1)/2 -(n-1)

=(n-1)(n-2)/2

option A)
selected by
0 votes
0 votes

If A’ is connected,it means surely A is disconnected, that's boils down to finding maximum no of edges in disconnected graph option A

Related questions

5 votes
5 votes
2 answers
1
Nidhi Budhraja asked Aug 26, 2018
2,379 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...
2 votes
2 votes
0 answers
2
raviyogi asked Jan 18, 2018
411 views
Is there any algorithm to find number of different minimum spanning trees for a graph?
1 votes
1 votes
2 answers
3
akankshadewangan24 asked Jul 8, 2017
825 views
can we say a null graph is eulerian circuit and hamiltonian circuit?
2 votes
2 votes
2 answers
4
rahul sharma 5 asked Jun 12, 2017
1,984 views
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?