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 .