title: Prove NP-completeness of CLIQUE-OR-INDEPENDENT-SET
body: <p>First of all, I want to mention that this is my <strong>homework</strong>. However, to solve my problem I can use any literature I want.</p>
  
  <p>Even though I think that problem is clear from its name, I will give it description: <em>"For given undirected graph G and given integer k, does G contain totally connected (clique) subgraph of size k or totally disconnected subgraph (independent set) of size k."</em></p>
  
  <p>I know about polynomial reductions from <code>3-SAT</code> to <code>CLIQUE</code> and from <code>3-SAT</code> to <code>INDEPENDENT-SET</code>. (<a href="http://mlnotes.com/2013/04/29/npc.html" rel="nofollow">http://mlnotes.com/2013/04/29/npc.html</a>) However, I have problem with this one because I cannot combine those two reductions. I also tried reduction from <code>CLIQUE</code> to <code>CLIQUE-OR-INDEPENDENT-SET</code> but without much success.</p>
  
  <p>So I would really appreciate any hints!</p>
  
  <p>Thanks in advance.</p>