# A graph connectivity problem (restated)

Given an undirected connected graph, our goal is to remove some edges to make the graph disconnected. The constraint is that each node of the graph can not lose more than $m$ edges incident to it. I want to find the minimum $m$ for which the goal is achievable. Is there any efficient algorithm to compute this minimum $m$ (and/or which edges to remove)? Or is it NP-complete?

-