# Finding maximum subgraph with vertices of degree at most k

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?