graph

Question

Assume undirected graph G is connected . G has 6 vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guaranteee that it will become disconnected

Comments

a  connected graph with $n$ vertices must have atleast $n-1$ edges, any edge less and it will be disconnected. In your question the number of vertices is 6, so to make it disconnected we must reduce the no. of edges to 5-1=4 (minimum), here we have 10 edges, so we must remove 6 edges. Is this is the correct answer $?$

---

3 ?? take a graph with 6 vertices and 10 edges such that if 9 edges are used  each vertex has degree three and adding 1 edge to it makes 2 vertices degree 4 .

minimum number of edges whose deletion ==> edge connectivity <=min (degree) = 3

---

@vivek u are correct

---

Change your comment to answer @Digvijaysingh Gautam

---

yes 6 correct answer

---

@Gautam wrt to your answer.

Will removing 3 edges gaurantee to make it disconnected? Consider what if I remove any 3 edges from vertex with degree 5 i.e 1st vertex in your case. Does it make it disconnected? No.

Now, to solve the problem, we must take worst case i.e try to make the graph complete graph as far as possible and assign the edges  to each vertex until no more edges can be assigned to that vertex.

e.g 5 + 3 + 3+ 3 +3 +3

Now, First I will remove all the internal edges i.e non-bordering edges. So, 4 edges are removed.

Now, we are left with cyclic graph with 6 vertices. So, to make it disconnected, I need to remove 2 more edges.

So, to gaurantee, 4+2 = 6 vertices must be removed.

Answer 1

We know : 

A tree is a minimally connected acyclic graph which contains n vertices and (n-1) edges..

Hence if a graph of n vertices contain less than (n-1) edges , then it will always guarantee that the resulting graph is disconnected..

So given we have 6 vertices and 10 edges at present..So 

Minimum number of edges required for connectivity  =  5 edges..

So if a graph contains 4 edges it will be disconnected.

Hence no of edges that need to be deleted   =    10  -  4    =   6

Comments

@Habib Sir

Graph with 6 vertices and 10 edges can be made with degree sequence <4,4,3,3,3,3>

after removing 3 edges my graph become disconnected with 5 vertices on one set and a 6th vertex on another,

so minimum should be 3 edges?

please guide

---

@learner_jai

Look at the "Always guarantee" term in the question.

For the example you take it might happen, you required 3 edges removal. But it is not true for all the graph.

---

@Hemant Parihar,
Thanks
These silly mistakes, I try to reduce it.

---

Superb explanation  Habibkhan

Answer 2

Number of edges in graph = 10

So sum of indegree of all vertices = 10*2 = 20

let a,b,c,d,e,f be the indegree of 6 vertices

So a+b+c+d+e+f = 20

Now, consider the following values of this variables

5 + 3 + 3 + 3 + 3 + 3 = 20

that means minimun indegree here is 3

So if we remove 3 edges from that vertex then the graph will become disconnected.

From above example we conclude that removing only 1 or 2 edges will not make the graph disconnected.

Now let us assume that removing 3 edges will also not make the graph disconnected. That means vertices in the graph have indegree greater than 3. That means the vertices have indegree 4 or 5 only. Lets us assume that 'x' vertices have indegree 4 and 'y' vertices have indegree 5. Then the two possible equations that they must satisfy are:

4x + 5y =20 and-----------------------------( sum of indegree of all vertices =20 )

x + y =6------------------------------------( total number of vertices = 6 )

if u solve this we will not get valid value of x and y

That means we cant make the graph having vertices with indegree only 4 or 5.

Hence answer should be 3.

Comments

i am totally confused what is the answer 3 or 6.
i am not getting till now.
i think 3 may be ans bu not sure.

---

3 for sure

Answer 3

see 3 is correct but not 6,5,4,3,2,1  why reason is 

first for 6 , given no of vertices is 6 in simple graph 'n' vertices maximum degree is n-1 means as given 6 vertices and  one vertex should have maximum 5 edges  so 6 edges not possible in case of minimum

second for 5 , only degree sequence possible is 5,3,3,3,3,3 so in this graph minimum degree is 3 whose removal makes graph disconnected 

third for 4 ; degree sequence possible is 4,4,4,4,2,2 , so in this graph minimum degree is 2 whose removal makes garph disconnected

forth for 3, same above 5,3,3,3,3,3 so min degree is 3

fifth for 2 ; degree sequence possible is 4,4,4,4,2,2 same above

sixth for 1; no degree sequence possible

so total 2 graph possible 1st have degree sequence is 4,4,4,4,2,2 let named is G1

2nd have degree sequence is 5,3,3,3,3,3 let named is G2

in G1 '2' edges removal graph disconnected and G2 '3' edges  removal graph disconnected 

now what should be the answer see question  "minimum number of edges whose deletion from graph G is always guarantee"  now removing min edge 2 work only for G1 not G2 bu  removing min edge 3 always guarantee for G1 as well as G2  so ans is 3 minimum edge