# Definition of a Category with Graphs relating to Morphisms

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.

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.

• 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)? May 23, 2018 at 12:05
• 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)$. May 23, 2018 at 12:31