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 Mathematical Logic graph-connectivity + – Sarvottam Patel asked Aug 19, 2016 Sarvottam Patel 639 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Sarvottam Patel commented Aug 19, 2016 reply Follow Share I am getting option a , but by substitution , what is the standard way to solve it. I solve it for n=3,4 ,5 and got option a 0 votes 0 votes vijaycs commented Aug 19, 2016 reply Follow Share think like ... you have a grapg A with n vertices. excepts one vertex, all n-1 vertices are making a complete graph with total (n-1)(n-2)/2 edges. Now if we see complement of this graph then it would be connected right ( A' ->star graph)?? And if we add any more edge in A, then it would make its complement disconnected ... Note- we are not told that A is also connected.. only A' is connected. just give it think .. 1 votes 1 votes Please log in or register to add a comment.
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) Sanket_ answered Aug 19, 2016 • selected Aug 19, 2016 by vijaycs Sanket_ comment Share Follow See 1 comment See all 1 1 comment reply Sushant Gokhale commented Sep 8, 2016 i reshown by Sushant Gokhale Sep 8, 2016 reply Follow Share option A is correct. 0 votes 0 votes Please log in or register to add a comment.
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 s_dr_13 answered Mar 12, 2022 s_dr_13 comment Share Follow See all 2 Comments See all 2 2 Comments reply Kabir5454 commented Mar 12, 2022 reply Follow Share I believe the following statement is wrong. If $\bar{A}$ is connected does not mean A is always disconnected. There is a theorem that : The complement of a disconnected graph is connected. but it does not mean if a graph is connected then its complement also disconnected. A counter example for this argument:- now you can see here both G and $\bar{G}$ are connected. Now for calculating max no of edge you can check the above best answer approach. 0 votes 0 votes s_dr_13 commented Mar 12, 2022 reply Follow Share Yea right my bad 😣 ! The complement of a disconnected graph is always connected but the complement of a connected graph may be connected or disconnected. Comes from the fact that at least of one of G or G’ is connected or both G and G’ can't be disconnected at the same time Thanks for correcting me 0 votes 0 votes Please log in or register to add a comment.