In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

**Definition.** Let and be graphs. Then the graph has vertices , and an edge from to if and only if implies (where we allow as usual).

**Lemma.** *If , , and are graphs, then there is a natural isomorphism*

*In other words, is the internal Hom in the symmetric monoidal category .*

*Proof**.* There is a bijection

So it suffices to show that is a graph homomorphism if and only if is. The condition that is a graph homomorphism means that for any , the functions have the property that implies . This is equivalent to for all and all . By the construction of the product graph , this is exactly the condition that is a graph homomorphism.

Because the symmetric monoidal structure on is given by the categorical product, it is customary to refer to the internal as the *exponential graph* .

**Example 1.** Let be the discrete graph on a set . Then is the complete graph with loops on the set . Indeed, the condition for two functions to be adjacent is vacuous since has no edges.

In particular, any function is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function is a graph homomorphism, since is a discrete graph.

**Example 2.** Conversely, is discrete as soon as has an edge, and complete with loops otherwise. Indeed, the condition

can only be satisfied if , and in that case is true for all and .

In particular, a function is a graph homomorphism if and only if either or has no edges. Under the adjunction above, this corresponds to the fact that a function is a graph homomorphism to if and only if has no edges, which means either or has no edges.

**Example 3.** Let be the discrete graph on a set with loops at every point. Then is the -fold power of . Indeed, the condition that two functions are adjacent is that for all , which means exactly that for each of the projections .

In particular, graph homomorphisms correspond to giving graph homomorphisms . Under the adjunction above, this corresponds to the fact that a graph homomorphism is the same thing as graph homomorphisms , since is the -fold disjoint union of .

**Example 4.** Let be the terminal graph consisting of a single point with a loop (note that we used instead for in this earlier post). The observation above that also works the other way around: . Then the adjunction gives

This is actually true in any symmetric monoidal category with internal hom and identity object . We conclude that a function is a graph homomorphism if and only if has a loop at . This is also immediately seen from the definition: has a loop at if and only if implies .

**Example 5.** Let and be the complete graphs on and vertices respectively. Then has as vertices all -tuples , and an edge from to if and only if when . For example, for we get an edge between and if and only if and .