In our graph theory course notes there is a statement:

"This series of results, beginning with the definition of a morphism of graphs, demonstrates that we have a category with graphs as the objects and maps of graphs as the morphisms."

We are asked to find out what this means. Can anyone break down the definition of a category and how it relates to this statement regarding graphs and morphisms?

In our course we define a graph by the triple $ G=(V,E,\epsilon) $

Where $V$ are the set of vertices, $E$ the set of edges and $\epsilon$ the map relating the two sets.


1 Answer 1


Not sure whether this is useful for you.

In the theory of categories the category of graphs usually has multiple digraphs as objects. They can be denoted as $\langle V,E,s,t\rangle$ where $r,s:E\to V$. If $e\in E$ then it is a directed edge starting at source $s(e)\in V$ and ending at target $t(e)\in V$.

In that context a morphism with domain $\langle V,E,s,t\rangle$ and codomain $\langle V',E',s',t'\rangle$ is a pair of functions $\langle D_v,D_e\rangle$ where $D_v:V\to V'$ and $D_e:E\to E'$ such that $D_v\circ s=s'\circ D_e$ and $D_v\circ t=t'\circ D_e$.

This construction carries the characteristics of a category.

It induces a category for undirected multiple graphs if we take as objects $\langle V,E,s,t,i\rangle$ where $i:E\to E$ is an involution (i.e. satisfies $i\circ i=\mathsf{id}_E$) with $s\circ i=t$ and (consequently) $t\circ i=s$ and demand that a morphism $\langle D_v,D_e\rangle:\langle V,E,s,t,i\rangle\to\langle V',E',s',t',i'\rangle$ respects the involutions in the sense that $D_e\circ i=i'\circ D_e$.

In that situation the distinction between source and target (so the direction) is somehow made irrelevant.

  • $\begingroup$ Thank you for your response. Am I right in thinking that a category is a directed graph, where objects are nodes/vertices and the arrows/edges are morphisms which connect objects? In the context of your example, the objects would be (V,E,s,t) and (V',E',s',t') and the arrow connecting them is the morphism (Dv,De)? $\endgroup$
    – Charlie W
    May 23, 2018 at 12:05
  • $\begingroup$ It is not so that a category is a directed graph. But it is so that there is a category that has directed graphs as objects. There indeed the objects are tuples $(V,E,s,t)$ and the arrows are ordered pairs $(D_v,D_e)$. $\endgroup$
    – drhab
    May 23, 2018 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .