I have the following problem, where $k$ is a fixed integer.


**Input:** Graph $G$.


**Output:** Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$. 


Do you know the complexity of this problem?



Minimum number of edges to remove to have low degree
If you also insist that the bounded-degree subgraph is connected, then your problem is NP-Hard, since it includes the Longest Path problem when $k=2$.


On the other hand, without the connectivity constraint, your problem can be solved in polynomial-time using standard techniques from matching theory. See this [paper](http://www.math.ens.fr/~amini/Publications/DAM.pdf) of Amini, Peleg, Pérennes, Sau and Saurabh, where they give the book *Matching Theory* by Lovász and Plummer as one reference to the polynomial result. 


