# "Canonical" graph structure on $\text{Hom}(G, H)$

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 to a similar question in the category of topological spaces.)

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 (which is rather unfortunately named from the perspective of category theory).
• No, the counterexample coming from the adjoint of a projection still rules that out. By the way, if there were an exponential object (as there is in the category of graphs with loops), its vertex set would not be $\operatorname{Hom}(G,H)$, but the set of all maps from $V(G)$ to $V(H)$ (since $\bullet\times G$ is $G$ with all its edges removed). The graph-homomorphisms would just be those vertices of the exponential object that have loops. This reflects the fact that (in the category of graphs with loops) the terminal object is a vertex with a loop, not just a vertex. Jul 10, 2015 at 13:33