$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$

Construction (The Path Category). Let $G$ be a directed graph (Definition For each edge $e \in \operatorname{Edge}(G)$, we let $s(e), t(e) \in \operatorname{Vert}(G)$ denote the source and target of $e$, respectively. If $x$ and $y$ are vertices of $\operatorname{Vert}(G)$, then a path from $x$ to $y$ is a sequence of edges $(e_ n, e_{n-1}, \ldots , e_1)$ satisfying

\[ s(e_1) = x \quad \quad t(e_ i) = s(e_{i+1}) \quad \quad t(e_ m) = y, \]

By convention, we regard the empty sequence of edges as a path from each vertex $x \in \operatorname{Vert}(G)$ to itself.

We define a category $\operatorname{Path}[G]$ as follows:

  • The objects of $\operatorname{Path}[G]$ are the vertices of $G$.

  • For every pair of vertices $x,y \in \operatorname{Vert}(G)$, we let $\operatorname{Hom}_{ \operatorname{Path}[G]}(x,y)$ denote the set of all paths $(e_ m, \dots , e_1)$ from $x$ to $y$.

  • For every vertex $x \in \operatorname{Vert}(G)$, the identity morphism $\operatorname{id}_{x}$ in the category $\operatorname{Path}[G]$ is the empty path from $x$ to itself.

  • Let $x,y,z \in \operatorname{Vert}(G)$. Then the composition law

    \[ \circ : \operatorname{Hom}_{\operatorname{Path}[G]}( y, z) \times \operatorname{Hom}_{\operatorname{Path}[G]}(x,y) \rightarrow \operatorname{Hom}_{\operatorname{Path}[G]}( x,z) \]

    is described by the formula

    \[ (e_ n, \cdots , e_1 ) \circ (e'_{m}, \ldots , e'_{1} ) = (e_{n}, \cdots , e_1, e'_{m}, \ldots , e'_{1}). \]

    In other words, composition in $\operatorname{Path}[G]$ is given by concatentation of paths.

We will refer to $\operatorname{Path}[G]$ as the path category of the directed graph $G$.