nLab
category of simple graphs

Introduction

Both category theory and graph theory study patterns based on diagrams consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists.

This article is a modest bridge, indicating that the category of graphs (in the usual graph-theorist’s sense – see for example Diestel) has some very nice properties.

Simple graphs as relations

By a simple graph, we mean a set $V$ equipped with a symmetric reflexive relation $E$. Morphisms between simple graphs are functions which preserve the given relations. Elements of $V$ are called vertices. Write $E(x,y)$ to say $(x,y)\in E$.

When drawing graphs, we put an edge between vertices $x$, $y$ iff $x\ne y$ and $E(x,y)$. In particular, we will not bother drawing an edge between $x$ and itself; we can think of it as tacitly there if we like. Perhaps better yet, that tacit edge can be thought of as a path of length $0$ from $x$ to itself (and who bothers drawing a path of length $0$?). In any case, it is clear that there is a natural bijection between

• simple graph structures on $V$ in the graph-theorist’s sense (i.e., graphs that are undirected, loop-free, and with at most one edge between two vertices), and

• reflexive symmetric relations on $V$;

thus we are within our rights to identify these two concepts.

This maneuver allows a simple definition of morphism as a function (between the sets of vertices) that preserves the edge relation:

$$(x,y)\in E_G\Rightarrow (f(x),f(y))\in E_H.$$(x,y) \in E_G \;\Rightarrow\; (f(x),f(y)) \in E_H .

This then includes natural operations like edge contractions as quotients. Namely, if $f:G\to H$ is a morphism as defined above, and if we have $G(x,y)$ and $f(x)=f(y)=v$, we still have $H(f(x),f(y))$ by default, so we can think of $f$ as contracting the edge between $x$ and $y$ in $G$ down to an edge of length $0$ between $v$ and itself in $H$.

The category of simple graphs is denoted by $\mathrm{SimpGph}$.

Properties of $\mathrm{SimpGph}$

The category $\mathrm{SimpGph}$ has very good properties. For example,

Theorem

$\mathrm{SimpGph}$ is a Grothendieck quasitopos. In particular, it is a regular category and even a logos. It is also $\mathrm{\infty }$-extensive.

See for example Adamek and Herrlich.

It is easy to describe monos and epis in $\mathrm{SimpGph}$. For, let $\mathrm{Vert}:\mathrm{SimpGph}\to \mathrm{Set}$ be the underlying vertex-set forgetful functor. We have two easy results:

Proposition

$\mathrm{Vert}$ reflects monos and epis (because $\mathrm{Vert}$ is faithful).

Proposition

$\mathrm{Vert}$ preserves limits and colimits (because it has a left adjoint $\mathrm{Disc}$ and a right adjoint $\mathrm{Codisc}$).

It follows that $\mathrm{Vert}:\mathrm{SimpGph}\to \mathrm{Set}$ both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in $\mathrm{SimpGph}$. For instance:

Lemma

In $\mathrm{SimpGph}$, the pushout of any mono is a mono.

Proof

Suppose we have a pushout diagram in $\mathrm{SimpGph}$:

$$\begin{array}{ccc}G& \to & H\\ {}^{\mathrm{mono}}\downarrow & & {\downarrow }^k\\ G\prime & \to & H\prime \end{array}$$\array{ G & \to & H \\ ^\mathllap{mono} \downarrow & & \downarrow^\mathrlap{k} \\ G' & \to & H' }

Since $\mathrm{Vert}$ preserves both pushouts and monos, and since the pushout of a mono in $\mathrm{Set}$ is a mono, we have that $\mathrm{Vert}(k)$ is monic in $\mathrm{Set}$. Since $\mathrm{Vert}$ reflects monos, this means $k$ is monic in $\mathrm{SimpGph}$.

Equalizers and coequalizers

If $f,g:G\overrightarrow{\to }H$ are maps in $\mathrm{SimpGph}$, then their equalizer $\mathrm{Eq}(f,g)=i:K\to G$ is given at the vertex level by

$$\mathrm{Vert}(i)=\mathrm{Eq}(\mathrm{Vert}(f),\mathrm{Vert}(g))$$Vert(i) = Eq(Vert(f), Vert(g))

and at the edge level by $K(x,y)\iff G(i(x),i(y))$; in other words, if $x,y$ belong to $K$ and there is an edge between them in $G$, then that edge lies in $K$. To express this last condition, we say the subgraph $i$ is full (at the edge level).

Thus, $i$ is a regular mono in $\mathrm{SimpGph}$ iff both $\mathrm{Vert}(i)$ is monic in $\mathrm{Set}$ and $i$ is full at the edge level.

The coequalizer of $f$ and $g$, say $\mathrm{Coeq}(f,g)=q:H\to Q$, is given at the vertex level by

$$\mathrm{Vert}(q)=\mathrm{Coeq}(\mathrm{Vert}(f),\mathrm{Vert}(g))$$Vert(q) = Coeq(Vert(f), Vert(g))

and at the edge level by taking the image of the composite $E_H\hookrightarrow \mathrm{Vert}(H{)}^2\stackrel{q^2}{\to }\mathrm{Vert}(Q{)}^2$, so that

$$Q(x,y)\iff {\exists }_{u,v}H(u,v)\wedge q(u)=x\wedge q(v)=y.$$Q(x, y) \Leftrightarrow \exists_{u, v} H(u, v) \wedge q(u) = x \wedge q(v) = y.

Thus, $q$ is a regular epimorphism if it is surjective at both the vertex and edge levels.

Ternary factorization

The category of simple graphs has a ternary factorization system as follows: each morphism $f:G\to H$ factors as

$$G\stackrel{q}{\to }G\prime \stackrel{a}{\to }H\prime \stackrel{i}{\to }H$$G \stackrel{q}{\to} G' \stackrel{a}{\to} H' \stackrel{i}{\to} H

where

• $q$ is a surjection between vertex-sets and at the edge level, i.e., is a regular epi;

• $a$ induces an identity between vertex-sets (hence is jointly monic and epic), but without necessarily being full at the edge level;

• $i$ is given by an injection between vertex-sets and is full at the edge level, and (thus) is a regular mono.

The factorization of $f$ into $q$ followed by $i\circ a$ is the (regular epi)-mono factorization, while the factorization of $f$ into $a\circ q$ followed by $i$ is the epi-(regular mono) factorization. To round out the discussion, we prove that regular monos are stable under pushout (which ensures that the epi-(regular mono) factorization is an orthogonal factorization system).

Lemma

In $\mathrm{SimpGph}$, the pushout of any regular monomorphism along any map is a regular mono.

Proof

Let $j:G\to H$ be a regular mono in $\mathrm{SimpGph}$, and let $f:G\to G\prime$ be any map. Form the pushout of the pair $(j,f)$ as a coequalizer diagram

$$G\stackrel{\stackrel{i_1\circ j}{\to }}{\underset{i_2\circ f}{\to }}H\bigsqcup G\prime \stackrel{q}{\to }H\prime$$G \stackrel{\overset{i_1 \circ j}{\to}}{\underset{i_2 \circ f}{\to}} H \sqcup G' \stackrel{q}{\to} H'

where $i_1:H\to H\bigsqcup G\prime$, $i_2:G\prime \to H\bigsqcup G\prime$ are the coproduct inclusions. We are trying to show that $q\circ i_2$ is a regular mono. Certainly $\mathrm{Vert}(q{i}_2)$ is monic in $\mathrm{Set}$ (again since $\mathrm{Vert}$ preserves monos and pushouts), so we just have to check that $q{i}_2$ is full at the edge level. So, suppose $H\prime (q{i}_2(x),q{i}_2(y))$; we must show $G\prime (x,y)$. According to how we form coequalizers $q$, there exist $u,v\in H\bigsqcup G\prime$ such that $q(u)=q{i}_2(x)$, $q(v)=q{i}_2(y)$, and $(H\bigsqcup G\prime )(u,v)$. Since $H$ and $G\prime$ are embedded disjointly in their coproduct, we have that

• either both $u$ and $v$ belong to the $G\prime$-component, in which case $u=i_2(x)$ and $v=i_2(y)$ (but in that case we’re done because $G\prime (x,y)$ follows from $(H\bigsqcup G\prime )(i_{2}x,i_{2}y)$, according to how the coproduct $H\bigsqcup G\prime$ is constructed);

• or both $u$ and $v$ belong to the $H$-component. But according to how pushouts are constructed at the vertex level, this means there exist $g_1,g_2\in G$ such that $f(g_1)=x$, $j(g_1)=u$ and $f(g_2)=y$, $j(g_2)=v$. Since $H(u,v)$, or $H(j(g_1),j(g_2))$, and $j$ is full at the edge level (because it is a regular mono), we have $G(g_1,g_2)$, and therefore $G\prime (f(g_1),f(g_2))$ or $G\prime (x,y)$, as desired.

Theorem

$\mathrm{SimpGph}$ is co-regular, i.e., ${\mathrm{SimpGph}}^{\mathrm{op}}$ is regular.

Proof

This is obvious from the first definition of “regular” given here.

References

• Reinhard Diestel, Graph Theory (Second Edition), Graduate Texts in Mathematics 173, Springer (2000).

• Jiri Adamek and H. Herrlich, Cartesian closed categories, quasitopoi, and topological universes. Comm. Math. Univ. Carol., Vol. 27, No. 2 (1986), 235-257. (web)

category: category