how can i prove that for every graph $G$, the clique $K_n$ is homomorphic to $G$ iff $G$ contains $K_n$ as an isomorphic subgraph?

Question

I need to prove that for every graph $G=(V,E)$, the clique $K_n$ is homomorphic to $G$ if, and only if $G$ contains $K_n$ as an isomorphic subgraph. How can i do this?

Answer 1

First thing we want to do here, is start with the relevant definitions relating to graph homomorphisms:

A graph homomorphism $f$ from a graph $G = (V(G), E(G))$ to a graph $H = (V(H), E(H))$, written $f : G → H$ is a function from $V(G)$ to $V(H)$ that maps endpoints of each edge in $G$ to endpoints of an edge in $H$. Formally, $\{u,v\} \in E(G)$ implies $\{f(u),f(v)\} \in E(H)$, for all pairs of vertices $u, v \in V(G)$.

If there exists any homomorphism from $G$ to $H$, then $G$ is said to be homomorphic to $H$...

We're talking about the special case of $K_n$: a complete graph. A homomorphism $f$ from $K_n$ to $G$ satisfies $f(i) \neq f(j)$ whenever $i \neq j$ (i.e., $f$ is a bijection), since if $f(i)=f(j)$, then $\{f(i),f(j)\}$ is not an edge in $G$, and $f$ is not a homomorphism.

So...

• One direction: If there is a edge-preserving bijection $f$ from the vertices of $K_n$ to some $n$ vertices of $G$, then we want to show those $n$ vertices induce a $K_n$ subgraph in $G$.

• The other direction: If $G$ has a subgraph $H$ isomorphic to $K_n$, then we want to show there is an edge-preserving bijection $f$ from the vertices of $K_n$ to the vertices of $H$.