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
.