graphs

Question

consider a complete garph on 2^(log(2^10)) vertices then the minimum number of edge removal operations needed to make graph disconnected

Comments

1023?

---

if the base of log is 2

then it is 1023

---

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

n² - 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 !