Assumed undirected graph G is connected. G has $6$-vertices and $10$ edges.
What will be the minimum number of edges whose deletion from graph G is always guaranteed that it will become disconnected ?
I randomly tried for many graphs and can say that removing $3$ edges from most of them produces disconnected graph.
But, I don't have any proof or generalization to confirm this ? Is this correct ?
Best Answer
Hint: what is the average degree of your graph? There must be a vertex of at or below average degree. Try to disconnect this vertex from the graph.