A constructive solution works. We take a candidate set S, which starts as the whole graph, and iteratively reduce it removing invalid nodes until we arrive at the solution. At each point, if some node in S has less than k adjacent nodes in S, remove it and decrease the degree of all nodes adjacent to it by 1.

This works because every node you remove has no chance to be in the solution set, and the final set will be a solution.