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?
Let $G$ be any graph and let $k = 0$.
This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.
It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.