This is a first post about some categorical properties of graphs (there might be a few more).
Definition. For us, a graph is a pair where
is a set and
is a collection of subsets of
of size
or
. An element
with
is called an edge from
to
, and a singleton
is a loop at
(or sometimes an edge from
to itself). If
, it is customary to write
and
.
A morphism of graphs is a map
such that
for all
. The category of graphs will be denoted
, and
will be called the forgetful functor.
Example. The complete graph on
vertices is the graph
where
and
is the set of
-element subsets of
. In other words, there is an edge from
to
if and only if
.
Then a morphism is exactly an
-colouring of
: the condition
for
forces
whenever
and
are adjacent. Conversely, a morphism
to a graph
without loops is exactly an
-clique in
: the condition that
has no loops forces
for
.
Lemma. The category has and the forgetful functor
preserves all small limits.
Proof. Let be a functor from a small category
, and let
be the limit of the underlying sets, with cone maps
. We will equip
with a graph structure
such that the maps
for
are morphisms and then show that the constructed
is a limit of
in
.
To equip with an edge set
, simply let
be the set of
of size
or
such that
for all
. Then this clearly makes
into a graph such that the
are graph morphisms for all
. Moreover, these maps make
into the limit cone over
: for any other cone
, the underlying maps
factor uniquely through
by the definition of
, and the construction of
shows that
is actually a morphism of graphs
.
Remark. Note however that does not create limits. On top of the construction above, this would mean that there is a unique graph structure
on
such that
is a cone over
. However, there are many such structures on
, because we can remove edges all we want (on the same vertex set
).
Example. As an example, we explicitly describe the product of two graphs
and
: by the lemma its vertex set is
. The ‘largest graph structure’ such that both projections
and
are graph morphisms is given by
if and only if
and
and
. This corresponds to the structure found in the proof of the lemma.
For a very concrete example, note that the product of two intervals/edges is a disjoint union of two intervals, corresponding to the diagonals in
. This is the local model to keep in mind.
The literature also contains other types of product graphs, which all have the underlying set . Some authors use the notation
for the categorical product or tensor product we described. The Cartesian product
is defined by
, so that the product of two intervals is a box. The strong product
is the union of the two, so that the product of two intervals is a box with diagonals. There are numerous other notions of products of graphs.
Remark. Analogously, we can also show that has and
preserves all small colimits: just equip the set-theoretic colimit with the edges coming from one of the graphs in the diagram.
Example. For a concrete example of a colimit, let’s carry out an edge contraction. Let be a graph, and let
be an edge. The only way to contract
in our category is to create a loop: let
be the one-point graph without edges, and let
be the maps sending
to
and
respectively. Then the coequaliser of the parallel pair
is the graph
whose vertices are
, where
is the equivalence relation
if and only if
or
, and whose edges are exactly the images of edges in
. In particular, the edge
gives a loop at the image
.
Remark. Note that the preservation of limits also follows since has a left adjoint: to a set
we can associate the discrete graph
with vertex set
and no edges. Then a morphism
to any graph
is just a set map
.
Similarly, the complete graph with loops gives a right adjoint to , showing that all colimits that exist in
must be preserved by
. However, these considerations do not actually tell us which limits or colimits exist.