Remove vertices until no edges are left
It sounds like you found the answer yourself, you are describing Vertex Cover, which in many ways are very similar to Independent Set, both problems are NP-complete.
The relation to Independent Set is that in a graph $G = (V,E)$, a set $S$ is a minimal vertex cover if and only if $V \setminus S$ is a maximal independent set.
If you know that Independent Set is NP-complete, then it follows that Vertex Cover is NP-complete too.
In other words, you are also looking for a maximum Independent Set.
Vertex cover.  Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at most $k$ such that all edges in $G$ are incident to a vertex in $S$?
Independent set.    Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at least $k$ such that the induced graph $G[S]$ has no edges?