Complexity status of the Edge Deletion problem to bounded degree graphs I'm interested in the complexity status of the following problem. 

Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$.

Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality at most $k$ such that the maximum degree of $G-E' = (V,E \setminus E')$ is at most $d$. No, otherwise.
Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval $[0,d]$ and that contains as many edges as possible. 

This problem is well-known to be solvable in polynomial time.
For instance, it is discussed in Chapter 10 (and in particular in Exercise  10.1.4) of the book  


  M.D. Plummer and L. Lovász:
  Matching Theory
  Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.