Given (finite, simple) graphs $G$, $H$ and $K$ and a [homomorphism](https://en.wikipedia.org/wiki/Graph_homomorphism)
$$
G+K\to H+K
$$
where $+$ denotes the [join](http://mathworld.wolfram.com/GraphJoin.html), does it follow that there also exists a graph homomorphism $G\to H$?


If this is known, I'd also appreciate a reference.



Cancelling a graph join from a graph homomorphism
If $|K|=\infty$, then this is false, as a counterexample $G=K\_2$, $H=K\_1$, $K=K\_\infty$ shows.


Let us prove that the claim is true if $K$ is finite (with no such assumption for $G$ and $H$). Induction on $|K|$; if $|K|=0$, the claim is trivial.


For the inductive step, consider a homomorphism $\psi\colon G+K\to H+K$. Set $G\_1=\psi(G)\cap K$, $K\_1=\psi(K)\cap K$, $H\_1=\psi(K)\cap H$. If $G\_1=\varnothing$, then $\psi\big|\_G$ is a required homomorphism $G\to H$. So now we assume that $|G\_1|>0$.


Each vertex of $G\_1$ is connected with each of $K\_1$ since $\psi$ is a homomorphism (thus in particulat $|K\_1|<|K|$). Each vertex of $H\_1$ is connected with each of $K\_1$ by the definition of join. Thus, the induced subgraphs on $G\_1\cup K\_1(\subseteq K)$ and $H\_1\cup K\_1$ are isomorphic to $G\_1+K\_1$ and $H\_1+K\_1$, respectively. So $\psi\big|\_{G\_1\cup K\_1}$ provides a homomorphism $G\_1+K\_1\to H\_1+K\_1$ which by the induction hypothesis implies the existence of a homomorphism $\varphi\colon G\_1\to H\_1$.


Finally, set $M=\psi(G)\cap H$. Each vertex of $M$ is connected with each of $K\_1$, since $\psi$ is a homomorphism. Thus the map $\eta\colon G\to H$, 
$$
 \eta(g)=\begin{cases}
 \psi(g), &\psi(g)\in M;\\
 \varphi(\psi(g)), &\psi(g)\in G\_1
 \end{cases}
$$
is a sought homomorphism. The step is proved.


