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.