Limits in the category of graphs

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 $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal P(V)$ is a collection of subsets of $V$ of size $1$ or $2$ . An element $\{x,y\} \in E$ with $x \neq y$ is called an edge from $x$ to $y$ , and a singleton $\{x\} \in E$ is a loop at $x$ (or sometimes an edge from $x$ to itself). If $G = (V,E)$ , it is customary to write $V(G) = V$ and $E(G) = E$ .

A morphism of graphs $f \colon G \to H$ is a map $f \colon V(G) \to V(H)$ such that $f(e) \in E(H)$ for all $e \in E(G)$ . The category of graphs will be denoted $\mathbf{Grph}$ , and $V \colon \mathbf{Grph} \to \mathbf{Set}$ will be called the forgetful functor.

Example. The complete graph $K_n$ on $n$ vertices is the graph $(V,E)$ where $V = \{1,\ldots,n\}$ and $E = {V \choose 2}$ is the set of $2$ -element subsets of $V$ . In other words, there is an edge from $x$ to $y$ if and only if $x \neq y$ .

Then a morphism $G \to K_n$ is exactly an $n$ -colouring of $G$ : the condition $f(e) \in E(K_n)$ for $e \in E(G)$ forces $f(x) \neq f(y)$ whenever $x$ and $y$ are adjacent. Conversely, a morphism $f \colon K_n \to G$ to a graph $G$ without loops is exactly an $n$ -clique in $G$ : the condition that $G$ has no loops forces $f(x) \neq f(y)$ for $x \neq y$ .

Lemma. The category $\mathbf{Grph}$ has and the forgetful functor $V \colon \mathbf{Grph} \to \mathbf{Set}$ preserves all small limits.

Proof. Let $D \colon \mathscr J \to \mathbf{Grph}$ be a functor from a small category $\mathscr J$ , and let $V = \lim V \circ D$ be the limit of the underlying sets, with cone maps $f_j \colon V \to V(D(j))$ . We will equip $V$ with a graph structure $G = (V,E)$ such that the maps $G \to D(j)$ for $j \in \mathscr J$ are morphisms and then show that the constructed $G$ is a limit of $D$ in $\mathbf{Grph}$ .

To equip $V$ with an edge set $E$ , simply let $E$ be the set of $e \subseteq \mathcal P(V)$ of size $1$ or $2$ such that $f_j(e) \in E(D(j))$ for all $j \in \mathscr J$ . Then this clearly makes $G = (V,E)$ into a graph such that the $f_j \colon G \to D(j)$ are graph morphisms for all $j \in \mathscr J$ . Moreover, these maps make $G$ into the limit cone over $D$ : for any other cone $g_i \colon H \to D(j)$ , the underlying maps $V(g_i) \colon V(H) \to V(D(j))$ factor uniquely through $g \colon V(H) \to V$ by the definition of $V$ , and the construction of $E(G)$ shows that $g \colon V(H) \to V$ is actually a morphism of graphs $g \colon H \to G$ . $\qedsymbol$

Remark. Note however that $V$ does not create limits. On top of the construction above, this would mean that there is a unique graph structure $G = (V,E)$ on $V$ such that $G$ is a cone over $G$ . However, there are many such structures on $V$ , because we can remove edges all we want (on the same vertex set $V$ ).

Example. As an example, we explicitly describe the product $G \times H$ of two graphs $G$ and $H$ : by the lemma its vertex set is $V(G \times H) = V(G) \times V(H)$ . The ‘largest graph structure’ such that both projections $p \colon G \times H \to G$ and $q \colon G \times H \to H$ are graph morphisms is given by $e \in E(G \times H)$ if and only if $|e| \in \{1,2\}$ and $p(e) \in E(G)$ and $q(e) \in E(H)$ . 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 $G = H = K_2$ is a disjoint union of two intervals, corresponding to the diagonals in $\{1,2\} \times \{1,2\}$ . This is the local model to keep in mind.

The literature also contains other types of product graphs, which all have the underlying set $V(G) \times V(H)$ . Some authors use the notation $G \times H$ for the categorical product or tensor product we described. The Cartesian product $G \square H$ is defined by $E(G \square H) = (E(G) \times V(H)) \cup (V(G) \times E(H))$ , so that the product of two intervals is a box. The strong product $G \boxtimes H$ 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 $\mathbf{Grph}$ has and $V$ 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 $G$ be a graph, and let $e = \{x,y\}$ be an edge. The only way to contract $e$ in our category is to create a loop: let $*$ be the one-point graph without edges, and let $f_x, f_y \colon * \to G$ be the maps sending $*$ to $x$ and $y$ respectively. Then the coequaliser of the parallel pair $f_x, f_y \colon * \rightrightarrows G$ is the graph $H$ whose vertices are $V(G)/\sim$ , where $\sim$ is the equivalence relation $a \sim b$ if and only if $a = b$ or $\{a,b\} = \{x,y\}$ , and whose edges are exactly the images of edges in $G$ . In particular, the edge $\{x,y\}$ gives a loop at the image $z = [x] = [y] \in V(H)$ .

Remark. Note that the preservation of limits also follows since $V$ has a left adjoint: to a set $S$ we can associate the discrete graph $S^{\operatorname{disc}}$ with vertex set $S$ and no edges. Then a morphism $S^{\operatorname{disc}} \to G$ to any graph $G$ is just a set map $S \to V(G)$ .

Similarly, the complete graph with loops gives a right adjoint to $V$ , showing that all colimits that exist in $\mathbf{Grph}$ must be preserved by $V$ . However, these considerations do not actually tell us which limits or colimits exist.

Lovely little lemmas

Or maybe ‘amusing observations’

Leave a Reply Cancel reply