Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset of its vertices. An induced graph $G[U]$ is graph created from $G$ by removing all vertices that are not part of the set $U$.
I want to find a polynomial time algorithm that has graph $G = (V, E)$ and integer $k$ as input and returns a maximum set $U \subseteq V$ with largest size such that all vertices of $G[U]$ have degree at most $k$.
My idea with greedy algorithm that removes vertices with largest degree or vertices connected with most vertices with degree greater than $k$ doesn't work.
Does anyone know how to solve this problem in polynomial time?