Construction 1.3.7.1 (The Path Category). Let $G$ be a directed graph (Definition 1.1.6.1). 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
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$.