Is finding if a graph has k isolated nodes a NP-Complete problem? I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem:


  Prove that the following problem is NP-Complete. Given a set of T
  transactions: $T = \{t_1,t_2,\dots,t_m\}$ where each transaction $t_i$ is a
  pair of banks $(b_{i1},b_{i2})$.  Find if, given an integer value k, there
  is a group of k banks that doesn't perform any of the given T transactions.


I was thinking to proceed this way: 


Input complete graph with all the Banks: $G=(B,E)$
Subtract to E the T set, I obtain a new graph, $G'=(B,E\setminus T)$
Find if there's an existing k-clique in $G'$


Is there any more effective way to solve this problem?
No, determining whether a graph has $k$ isolated vertices is not1 NP-complete. Just count the number of isolated vertices and compare against&nbsp;$k$. This can be done deterministically in linear time (linear in the size of the graph's description; possibly quadratic in the number of vertices).

1 Unless P=NP and, even then, it might not be NP-complete.