Is it NP-hard to find a maximum inpendent set in a graph of size >=|E|. |E| is the number of edges.
My thinking is that it is not possible that there is a independent set of size > |E|. But how hard is it to decide if there is a independet set of size exactly |E|?