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?



A graph connectivity problem (restated)
It appears to be NP-complete even when m=1: see The Complexity of the Matching-Cut Problem, Maurizio Patrignani and Maurizio Pizzonia, WG 2001, <http://dx.doi.org/10.1007/3-540-45477-2_26>


