# Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.

The $$k$$-clique problems asks whether there is a homomorphism from the $$k$$-clique to a given graph. Therefore in principle, given an instance $$\langle G,k \rangle$$ of $$k$$-clique, you can just output $$\langle K_k, G \rangle$$, which is an instance of graph homomorphism.
However, in general $$\langle K_k, G \rangle$$ could be much larger than $$\langle G,k \rangle$$, since encoding $$k$$ takes $$\Theta(\log k)$$ bits, whereas encoding $$K_k$$ probably takes $$\Theta(k^2)$$ bits (depending on your encoding). Assuming that graphs are encoded as adjacency matrices, the solution is to compare $$k$$ to the number of vertices in $$G$$. If $$k$$ is larger than the number of vertices in $$G$$, then the answer is No, and so you can output a fixed No instance (say $$K_2,K_1$$). Otherwise the size of the output instance is polynomial in the size of the input instance, and so there is no problem.