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)$).


For the edge set $E \subseteq [\text{Hom}(G,H)]^2$ I would like to pick 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.


**Questions**. 


1) Is this construction always possible? Does it have a name?


2) If this works, how does it compare with $E'\subseteq [\text{Hom}(G,H)]^2$ where $E'$ is defined by $E'=\big\{\{f,g\}\in [\text{Hom}(G,H)]^2: \{f(v), g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}$?


(For a more categorical description of this problem, see Todd Trimble's [answer](https://mathoverflow.net/a/210914/8628) to a similar question in the category of topological spaces.)



"Canonical" graph structure on $\text{Hom}(G, H)$
It is trivial that such a maximal $E$ exists, and consists of pairs $\{f,g\}$ such that whenever $x$ and $y$ are adjacent, $f(x)$ and $g(y)$ are adjacent. However, it does *not* make $\operatorname{Hom}(G,H)$ an exponential object, essentially because morally (according to the definition above) it should have a loop at every vertex. For instance, when $G=H$, then for any graph $K$, there is a projection map $K\times G\to G$. But the associated map $K\to \operatorname{Hom}(G,G)$ sends every point to the identity, and so is not a graph homomorphism unless $K$ has no edges.


Your $E'$ is adjoint not to the categorical product, but to the [Cartesian product](https://en.wikipedia.org/wiki/Cartesian_product_of_graphs) (which is rather unfortunately named from the perspective of category theory).


