By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A *graph homomorphism* between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.


Given graphs $G,H$, we denote by $\text{Hom}(G, H)$ the set of all graph homomorphisms $f: G\to H$. Note that for many $G, H$ the set $\text{Hom}(G,H)$ is empty (for instance when $\chi(G) > \chi(H)$).


Define $E\_1(G,H) \subseteq [\text{Hom}(G,H)]^2$ to be the largest set such that the evaluation map $e: \text{Hom}(G,H)\times G \to H$, defined by $(f,v) \mapsto f(v)$, is a graph homomorphism. (Here we consider the Cartesian product of graphs, and not the categorical product, see [this](https://mathoverflow.net/a/211193/8628) post.)


Moreover, let $E\_2(G,H) = \big\{\{f,g\}\in [\text{Hom}(G,H)]^2: \{f(v), g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}$.


Are there graphs $G,H$ such that neither $E\_1(G,H) \subseteq E\_2(G,H)$ nor $E\_2(G,H) \subseteq E\_1(G,H)$?



Two graph structures on $\text{Hom}(G,H)$
Here are two answers, depending on what you mean by $\times$, which was not clear to me from your wording.




---


Answer 1, assuming that $\times$ is the Cartesian product, or in other words, that the edges of $F\times G$ are of one of the two following forms: 


* $\{(x,v),(y,v)\}$ for $\{x,y\}\in E(F)$ and $v\in V(G)$
* $\{(x,u),(x,v)\}$ for $x\in V(F)$ and $\{u,v\}\in E(G)$.


In this case, your two structures coincide.


One can test whether $\{f,g\}$ is in $E\_1(G,H)$ by looking at the image under $e$ of all the putative edges it generates in $\mathrm{Hom}(G,H)\times G$; the pair $\{f,g\}$ is in $E\_1(G,H)$ if and only if all of these are in $E(H)$.


The set of putative edges is of the form $\{\{f,g\}\times v\}$ for $v\in V(G)$. Therefore, the pair $\{f,g\}$ is in $E\_1(G,H)$ if and only if $\{f(v),g(v)\}$ is in $E(H)$ for all $v\in V(G)$. But this is the definition of $E\_2(G,H)$.




---


Answer 2, assuming that $\times$ is the categorical product, or in other words, that the edges of $F\times G$ are of the form $\{(x,u),(y,v)\}$ for $\{x,y\}\in E(F)$ and $\{u,v\}\in E(G)$.


There are graphs where $E\_1(G,H)$ and $E\_2(G,H)$ are incomparable. Take $V(G)=\{1,2,3\}$ and $E(G)=\{\{1,2\}\}$. Take $V(H)=\{a,b\}$ and $E(H)=\{\{a,b\}\}$.


Then $\mathrm{Hom}(G,H)$ has four elements:


* $f\_1(1)=a;\quad f\_1(2)=b;\quad f\_1(3)=a$
* $f\_2(1)=a;\quad f\_2(2)=b;\quad f\_2(3)=b$
* $f\_3(1)=b;\quad f\_3(2)=a;\quad f\_3(3)=a$
* $f\_4(1)=b;\quad f\_4(2)=a;\quad f\_4(3)=b$


With this interpretation of $\times$ (which I believe corresponds with Eric Wofsey's in the linked question), $E\_1(G,H)$ is the set $\{\{f\_1,f\_2\},\{f\_3,f\_4\}\}$.


On the other hand, $E\_2(G,H)$ is $\{\{f\_1,f\_4\},\{f\_2,f\_3\}\}$.


