0 votes 0 votes consider a complete garph on 2^(log(2^10)) vertices then the minimum number of edge removal operations needed to make graph disconnected Mathematical Logic discrete-mathematics + – suneetha asked Nov 23, 2018 suneetha 261 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply raahul commented Nov 23, 2018 reply Follow Share 1023? 0 votes 0 votes Gurdeep Saini commented Nov 23, 2018 i reshown by Gurdeep Saini Nov 23, 2018 reply Follow Share if the base of log is 2 then it is 1023 0 votes 0 votes Shaik Masthan commented Nov 23, 2018 reply Follow Share let there are n vertices, Therefore complete graph contains $\binom{n}{2}$ with n, vertices, there should be atleast n-1 edges, for that vertices is connected ! For disconnecting the graph, it requires (n-1)-1 edges $\binom{n}{2}$ - x = n-2 $\frac{n(n-1)}{2}$ - x = n-2 n(n-1) - 2x = 2n - 4 n2 - n - 2x = 2n - 4 ===> x = $\frac{n^2\; - \;3n\; + \;4}{2}$ where x is minimum no.of any edges that removed, to make given graph is disconnected always. But, if there is no restriction on removing edges, then we can choose a vertex, and remove it's edges ==> n-1 edges are sufficient to make that graph is disconnected ! 0 votes 0 votes Please log in or register to add a comment.