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.