Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$. Proof that Combi is NP-complete.
I tried to reduce Clique <=p Combi. I had two different ideas:
Let $f(\langle G,k\rangle) = \langle G,k\rangle$ so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle)$ is trivial. Though I am puzzled with the case $f(\langle G,k\rangle) \in$ COMBI $\Rightarrow \langle G,k\rangle $. What is when I have only an Independent set $\geq k$ within $\langle G,k\rangle$ and no Clique $\geq k$. Then it would be in COMBI but not within CLIQUE.
Let $f(\langle G,k\rangle) = \langle G´,k\rangle$ where $G´= \overline{G} \cup G$ as disjunctive union (two different components) and $\overline{G}$ is the complement graph so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle) \in$ COMBI is trivial again, but the other case seems to be flawed due to the same reason as in the first try.
Where am I going wrong or do I have to make a completely different reduction $f$?