connectivity

Question

Consider a simple connected undirected graph G which has m vertices and n edges. Which of the following condition always guarantee that after removal of those number of edges graph will be disconnected?

a)m – n + 2

b)$_{2}^{m}\textrm{C}-n+2$

  c)n – 2

d)None of the above

Comments

No option is matching.

---

yes...i also think so d) should be the answer.... given ans is b)

my doubt-

whether the Q is asking minimum no . of edges  that should be removed to guarantee disconnection or any no. of edges that should be removed that guarantees disconnection.

---

Any minimum number of edges .

---

$$\begin{align*} &\text{If no of removed edges = x} \\ &\text{Then, } \\ &x \geq \left [ n-\frac{\left ( m-1 \right ).\left ( m-2 \right )}{2} \right ] \\ \end{align*}$$

 

correct ??

---

since number of edges is n, so if we remove n-2 edges then condition satisfies. only doesn't satisfy for m = 2.

---

@Debasish  I think not correct.

because , take a case of complete graph, which not satisfies equation.

The formula satisfies for disconnected graph e<=n-2

But how many edge we should remove to guarentee disconnection, cannot say.

Beacause there could be multiple edges between 2 vertices.

So, question is ambiguous

---

simple graph is not a multi graph. so there can't be multiple edges. right ?

---

$$\begin{align*} &\text{For k components ,} \\ &\Rightarrow \left ( n-k \right ) \leq e \leq \left [ \frac{\left ( n-k+1 \right )\left ( n-k \right )}{2} \right ] \\ &\text{To be disconnected ; existance of minimum 2 component is enough ,} \\ \\ &\text{Putting k = 2} \\ &\Rightarrow \left ( n-2 \right ) \leq e \leq \left [ \frac{\left ( n-2+1 \right )\left ( n-2 \right )}{2} \right ] \\ &\Rightarrow \left ( n-2 \right ) \leq e \leq \left [ \frac{\left ( n-1 \right )\left ( n-2 \right )}{2} \right ] \\ &\text{Now Assume e is at max for two component Or, } e = \left [ \frac{\left ( n-1 \right )\left ( n-2 \right )}{2} \right ] \\ & \text{If we add +1 edge to } e \\ &\text{Then graph becomes connected or one unit or single component} \\ \\ \hline \\ &\rightarrow \text{Now, If we have a single component with m vertices and n edges } \\ &\rightarrow \text{We remove x amount of edges till the graph becomes disconnected } \\ &\text{or just divided into two components } \\ \end{align*}$$

$$\begin{align*} &\text{No of egdes in these two components (n - x) together can not be more than } \\ & \text{this quantity } \left [ \frac{\left ( m-1 \right )\left ( m-2 \right )}{2} \right ] \\ &\Rightarrow \left ( n - x \right ) \leq \left [ \frac{\left ( m-1 \right )\left ( m-2 \right )}{2} \right ] \\ &\Rightarrow x \geq \left [ n - \left [ \frac{\left ( m-1 \right )\left ( m-2 \right )}{2} \right ] \right ] \\ \end{align*}$$

 

If there anything wrong or misleading ..please ..check or rectify ...

---

@ Debashish Deka

consider m=6 and n=10
your solution results in x>=0
and this is not correct

whenever we have to find minimum edges for disconnection we can simply remove the edges of minimum degree i.e.   x>= 2*n/m

---

the initial graph is connected.

you have taken "consider m=6 and n=10"

for connected graph we need $n-1$ = $9$ edges otherwise graph will be disconnected.. So you have taken a disconnected graph from starting.

Will it be ok ?? tell me ??

---

i have taken connected graph as given in the Question m  vertices i.e. 6 and n edges  i.e. 10

Answer 1

I think answer should be (n-m+2) => Choice d

Given m vertices and n edges.

Since it is connected, n >= m-1.

Let x edges be needed to be removed.

=> (m-1) edges needed to be a spanning tree. If any edge removed from it, then graph will be disconnected.

=> Final graph should have m-2 edges

=>  x= n-(m-2) = n - m + 2

And n-m+2>=1 (as n>=m-1), so no problem of it being <=0.