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?