Let $\mathrm{Graph}$ be the category of simple, undirected graphs with graph homomorphisms. For any graphs $G, H$ we denote by $\text{Hom}(G, H)$ the set of graph homomorphisms $f:G\to H$. (Note that $\text{Hom}(G, H)$ can be empty, for instance if $\chi(G) > \chi(H)$.)
We can make $\text{Hom}(G, H)$ into a graph by saying that $f, g: G\to H$ form an edge if and only if $\{f(v), g(v)\}\in E(H)$ for all $v\in V(G)$.
Is $\mathrm{Graph}$ cartesian-closed?
There are many categories of graphs, so perhaps it's best to take a synoptic view (though far from exhaustive).
The table below surveys several categories of directed multigraphs (DM), directed graphs (DG), undirected multigraphs (UM), and undirected graphs (UG). The asterisks indicate the ones which are not cartesian closed. There are many other interesting categories of graphs, some of which are mentioned in the comments.
The category of simple graphs is (16) in the chart and list below. It is not cartesian closed. But a slight modification of this category -- (15) below -- with equivalent objects but where morphisms are allowed to collapse an edge to a point, is cartesian closed.
However, the description of the internal hom given in the question is incorrect for any of the categories below (though it's a reasonable guess!). The internal hom $H^G$ has for vertices all functions $V(G) \to V(H)$ between vertex sets. An edge from $f$ to $g$ is a rule which assigns, to every edge $x \to y$ in $G$, an edge $f(x) \to g(y)$ in $H$ (of course, in graphs which are not multigraphs, there is always at most one edge $f(x) \to g(y)$ to choose, so that this is just a condition). This should be compared to the internal hom in chain complexes, $G$-representations, etc, where maps from the terminal / unit object are not quite the same as "points" or "elements" in the most obvious sense and the internal hom ends up bigger than one might think. The graph homomorphisms may be recovered from this by homming in from the terminal object. A subtle point is that e.g. if we dress up a simple graph to be a reflexive graph (moving from (16) to (15) or eqivalently (14) as suggested above), it's important to remember that we've done this when computing the internal hom via the above description, or when mapping in from the terminal object to recover the homomorphisms.
\begin{array}{lcccc} & DM & DG & UM & UG \\ \text{Loops allowed} & 1 & 5 & 9* & 13\\ \text{Loops allowed and reflexive} & 2 & 6 & 10* & 14\\ \text{strictly reflexive} & 3* & 7 & 11* & 15 \\ \text{Loops not allowed} & 4* & 8* & 12* & 16* \end{array} The concepts of reflexive and strictly reflexive graphs are distinct for multigraphs, but the same for graphs, which I forgot when writing. Nevertheless, the following should be accurate, just with unnecessarily complicated discussion for (7) (equivalent to (6)) and (15) (equivalent to (14)).
A particular salient point to keep in mind is:
Even if you're interested in, say, simple graphs, the notion of graph homomorphism might not be the correct notion of morphism to use. Changing the morphisms may be equivalent to equipping your graph with a bit of "dummy data" and using the resulting standard notion of homomorphism sometimes results in a better-behaved notion of morphism.
Warmup:
We're going to systematically go through all these different categories of graphs. To motivate the approach, consider for example the category of (1) directed multigraphs where loops are allowed. Such a graph $G$ comprises two sets $V(G),E(G)$ of vertices and edges respectively, and two functions $E(G) \rightrightarrows V(G)$, one of which sends an edge to its starting vertex, and the other to its ending vertex. This is data is nicely summarized by saying that we have a presheaf on the category $\mathcal I$ with two objects and two nonidentity morphisms which looks like this [1]:
$$V \rightrightarrows E$$
Presheaves come with a natural notion of morphism, and it agrees with the usual notion of a graph homomorphism. So we see that the category of directed graphs where loops are allowed is equivalent to the category of presheaves on the category $\mathcal I$. Therefore, as Dmitri Pavlov observes in the comments, it is cartesian closed.
Categories of Presheaves:
In the following, we'll consider presheaves on $\mathcal I$ as well as three other categories which we'll call $\mathcal R, \mathcal U, \mathcal T$, each of which has two objects $V,E$ and a finite number of morphisms. The categories of presheaves on these categories will be denoted $Psh(\mathcal I), Psh(\mathcal R),Psh(\mathcal U),Psh(\mathcal T)$.
The category $\mathcal I$ which we've already seen, can alternatively be described as (a skeleton of) the category of linearly ordered sets of cardinality 1 or 2, and all injective order-preserving maps. This category has 2 objects and 2 nonidentity morphisms. A presheaf on $\mathcal I$ is a directed graph.
The category $\mathcal R$, (a skeleton of) the category of linearly ordered sets of cardinality 1 or 2 and all order-preserving maps. This category has 2 objects and 5 nonidentity morphisms. A presheaf on $\mathcal R$ is a directed graph equipped with a distinguished loop at each vertex (and homomorphisms are required to carry distinguished loops to distinguished loops). Such a graph is called a (2) reflexive, directed multigraph where loops are allowed.
The category $\mathcal U$, (a skeleton of) the category of sets of cardinality 1 or 2 and all injective maps. This category has 2 objects and 3 nonidentity morphisms. A presheaf on $\mathcal U$ is a directed graph equipped with an involution on its edges which swaps the endpoints. We'll see that such structures are related to undirected multigraphs.
The category $\mathcal T$, (a skeleton of) the catgeory of sets of cardinality 1 or 2 and all maps. This category has 2 objects and 6 nonidentity morphisms. A presheaf on $\mathcal T$ is like a presheaf on $\mathcal U$, in addition has a designated loop at each vertex which is fixed by the involution. We'll see that such structures are related to reflexive, undirected multigraphs.
Generalities on Presheaf Categories: We will use the following facts:
Every presheaf category is cartesian closed.
Let $\mathcal D$ be a full reflective subcategory of a presheaf category $Psh(\mathcal C)$ containing the representable presheaves. Then $\mathcal D$ is cartesian closed if and only if $\mathcal D$ is an exponential ideal (i.e. $Y \in \mathcal D, X \in Psh(\mathcal C) \Rightarrow Y^X \in \mathcal D$).
Let $S \subseteq Mor (Psh(\mathcal C))$ be a set of morphisms, and let $\mathcal D \subseteq Psh(\mathcal C)$ be the right orthogonal complement to $S$. Suppose that $\mathcal D$ contains the representables. Then $\mathcal D$ is cartesian closed if and only if, for every representable $c$, every $i \in I$, and every $Y \in \mathcal D$, $Y$ is right orthogonal to $i \times 1_c$.
Below, all the categories we consider are full subcategories of presheaf categories conatining the representables (there are always just two representables -- the free point $V$ and the free edge $E$) and defined by explicit orthogonality conditions. In each case, to check the last condition for cartesian closedness, it will suffice to consider the case where $c$ is the free edge $E$. This can always be done by hand. Since it's hard to create the appropriate images and to post them here, I will just report what the verdict ends up being for cartesian closure.
Directed Graphs as Presheaves:
As we've seen, the category of directed multigraphs with loops allowed and homomorphisms is just $Psh(\mathcal I)$. As a presheaf category, it is cartesian closed. This is the category theorist's default notion of "graph".
As we've seen, the category of reflexive directed multigraphs with loops allowed is just $Psh(\mathcal R)$. As a presheaf category, it is cartesian closed. This type of graph is also commonly used in category theory.
The category of strictly reflexive directed multigraphs is the full subcategory of $Psh(\mathcal R)$ where there are no loops besides the designated ones (whenver I say "strictly reflexive" in this answer, that is what I mean -- reflexive, and the only loops are the designated ones). This is the right orthogonal complement to the map from the free loop to the terminal object. The product of this map with the free edge is not orthogonal to all strictly reflexive multigraphs, so strictly reflexive multigraphs are not cartesian closed.
The category of loop-free directed multigraphs may be regarded as a full subcategory of the category of directed multigraphs where loops are allowed. It lacks a terminal object, so is not cartesian closed.
Note that the objects of (3) and (4) are equivalent -- even if you don't like loops, you might pretend they're there for the sake of defining morphisms.
The category of directed graphs where loops are allowed is the full subcategory of directed multigraphs which is right orthogonal to the map from the graph that looks like this $\bullet \rightrightarrows \bullet$ to the free edge $\bullet \to \bullet$. This is an exponential ideal, so this category is cartesian closed.
The category of reflexive directed graphs where loops are allowed is the full subcategory of reflexive directed multigraphs which is right orthogonal to a similar map as in (5) (if we take the convention that designated loops are suppressed in drawings). This is an exponential ideal, so this category is cartesian closed.
The category of strictly reflexive directed graphs is the full subcategory of reflexive directed multigraphs which is right orthogonal to both the morphism of (6) and the morphism of (3). The morphism of (3), after taking the product with the free edge, was not orthogonal to every strictly reflexive directed multigraph, but it is orthogonal to every strictly reflexive directed graph. The other morphism also works out as in (6), so this category is an exponential ideal and hence cartesian closed.
The category of loop-free directed graphs may be regarded as a full subcategory of the category of directed graphs. It lacks a terminal object, and so is not cartesian closed.
Note again that the objects of (7) and (8) are equivalent. I think graph theorists are generally more likely to think about graphs as described in (8), but this time the trick of changing the morphisms to those of (7) buys us cartesian closure.
Undirected Graphs as Presheaves:
The category of undirected multigraphs where loops are allowed may be embedded into $Psh(\mathcal U)$ in at least two ways. The most obvious way is to do the obvious thing for vertices, and for each undirected edge, to put in two directed edges, exchanged by the involution. Unfortunately, this yields "spurious" morphisms which exchange the two copies we get of each loop. To fix this, we modify the construction by putting in only one directed edge for each loop, and have it fixed by the involution. This gives the right notion of morphism. Thus undirected multigraphs where loops are allowed form the full subcateory of $Psh(\mathcal U)$ right orthogonal to the map from the free loop (which is a point with two loops exchanged by the involution) to the terminal object (which is a point with a loop which is fixed by the involution). This is not an exponential ideal, and hence not cartesian closed.
The category of reflexive undirected multigraphs where loops are allowed is the full subcategory of $Psh(\mathcal T)$ defined by a similar orthogonality condition to (9). This category is not an exponential ideal, and so not cartesian closed.
The category of strictly reflexive undirected multigraphs is the full subcategory of $Psh(\mathcal T)$ satisfying the orthogonality condition of (10) as well as one similar to (3). It is not an exponential ideal, and so not cartesian closed.
The category of loop-free undirected multigraphs is the full subcategory of $Psh(\mathcal T)$ satisfying the orthogonality conditions of (11), plus one similar to (4). This category lacks a terminal object, and so is not cartesian closed.
Again the objects of (11) and (12) are equivalent.
The category of undirected graphs where loops are allowed is the full subcategory of $Psh(\mathcal U)$ which is right orthogonal to the map of (9) plus a map analogous to (5). As in (7), the non-multi-ness comes to the rescue -- this is an exponential ideal, and hence cartesian closed.
The category of reflexive undirected graphs where loops are allowed is the full subcategory of $Psh(\mathcal T)$ which is right orthogonal to maps analogous to (13). Similarly to (13), this is an exponential ideal, and hence cartesian closed.
The category of strictly reflexive undirected graphs is the full subcategory of $Psh(\mathcal T)$ which is right orthogonal to the maps of (14), plus the map of (11). This is an exponential ideal, and hence cartesian closed.
The category of loop-free undirected graphs may be regarded as a full subcategory of the category of undirected graphs where loops are allowed. This category lacks a terminal object, and hence is not cartesian closed.
(16) is the category of the question. As Wojowu observed in the comments, it lacks a terminal object, and so is not cartesian closed for trivial reasons. But (15) has equivalent objects to (16), with the morphisms differing only in that we allow an edge to be contracted to a point. With this change, the category becomes cartesian closed.
[1] Note the reversal in direction of the arrows because a presheaf is a functor $(V\rightrightarrows E)^{op} \to Set$ -- the reversal comes from the "op". The "op" is a matter of convention, but in this case is nice because it allows the definitions of the categories we use to be a bit slicker.
For the sake of completeness, the interested reader of this question can find more details in the following paper, which addresses in Section 4 the topic in question: "Categories of graphs are cartesian closed." There, the author considers four different categories of graphs. The paper follows a relatively similar exposition to Tim Campion's answer.
@article{Bumby1986,
title = {Categorical constructions in graph theory},
author = {Richard T. Bumby and Dana May Latch},
year = 1986,
journal = {International Journal of Mathematics and Mathematical Sciences},
url = {https://www.emis.de/journals/HOA/IJMMS/9/1.pdf}
volume = 9,
number = 1,
pages = {1--16},
doi = {10.1155/s0161171286000017}
}
You may be interested in the following thesis "Functorial Approach to Graph and Hypergraph Theory" by M. Schmidt looks at when categories of uniform hypergraphs have exponentials. In particular he gives the following conceptual equations:
Graphs + Exponentials = (X,M)-Graphs
Graphs + Effective Equivalence Relations = (X.M)-Graphs
where Graphs is a category of uniform hypergraphs and (X,M)-graphs is a category of presheaves on two objects (containers for vertices and arrows). I can't remember (or quickly find) if he looks at exponentials in these categories.
