# Degree constrained edge partitioning (version 2)

Given a graph $G=(V,E)$ with real-valued (positive or negative) weights assigned to its edges, we want to remove a set of edges so that the sum of the remaining edges is minimized and the degree of any vertex should be different than 1 (i.e. 0 or more than 1) in the final graph.

I'm interested in the complexity of this problem.

Note that this problem is a slight variation of this.

-
So there should be no leaf vertices in the final graph. Isolated vertices are OK. –  eakbas Apr 9 '10 at 1:10

It's not quite the same, but I think it's very similar to the "minimum subgraph of minimum degree ≥ d" problem in this paper, and like that problem is very likely to be NP-complete.

-
Didn't you show in you answer to the linked question that "minimum subgraph of degree $\ge 2$" is polynomial? –  Sergei Ivanov Apr 9 '10 at 8:41
The difference is that in this case one has to decide which vertices to include, and which to give degree zero. That makes it harder. –  David Eppstein Apr 9 '10 at 17:34