3 votes 3 votes The maximum number of possible edges in an undirected simple graph with $100$ vertices and $5$ components is ___ DS go-ds-1 data-structures graph-theory connected-components numerical-answers + – Arjun asked Oct 10, 2016 Arjun 503 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes Maximum number of possible edges in an undirected simple graph with 100 (N) vertices and 5 (K) components is => $\left ( N - K \right )\left ( N - K + 1 \right ) / 2$ => 4560 Kapil answered Oct 13, 2016 selected Jan 27, 2017 by Kapil Kapil comment Share Follow See 1 comment See all 1 1 comment reply cse23 commented Oct 16, 2016 reply Follow Share maximum no of edges is possible if we assign only one vertex to each component and at the last component we will assign all the vertices we know component is a tree to each component must have a root/one vertex 4 component has 4 vertices and at 5th component we are left with 96 vertices so maximum no. of edges = C (96,2) =4560 14 votes 14 votes Please log in or register to add a comment.