This problem is either in P or is NP Complete. Prove this is NP Complete, or prove it is in P.

In a graph, the degree of a vertex v, denoted d(v), is the number of edges that touch that vertex; the maximum degree of a graph is the maximum, over vertices v, of d(v).

This problem is a variant of INDEPENDENT SET in bounded-degree grap The language in question is the set of all pairs (G, k) for which G is a graph with maximum degree at most 4 containing an independent set of size at least k