0 votes 0 votes A graph G has k isolated vertices and n + k vertices. The maximum number of edges graph G can have? a) n(n-1) b)n(n-1)/2) c) n(n-k+1)/2 d) n(n+k-1)/2 cse23 asked Jan 20, 2017 cse23 466 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Kantikumar commented Jan 20, 2017 reply Follow Share It should be nC2 3 votes 3 votes ankyAS commented Jan 21, 2017 reply Follow Share is n+k is total number of vertices? the first statement seems ambigious 0 votes 0 votes Dhananjay2017 commented Jan 27, 2017 reply Follow Share For maximum number of edges . Divide graph into k component such a way that (k-1) components having 1 vertex and last component had remaining vertices . Last component will get (n+k-(k-1)) vertices i.e ; (n+1) verices . Maximum numbers of edges = (n+1)*(n)/2 There is no option 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Total number of vertices n+k Number of isolated vertex k Total components k+1, Maximum number of edges 0*K (For k isolated vertex) n(n-1)/2 for reaming 1 component Total Maximum Edges $\frac{(n*(n-1))}{2}$ Option B Tesla! answered Mar 29, 2017 Tesla! comment Share Follow See all 0 reply Please log in or register to add a comment.