We now generalize Proposition 1.1.5.14 to obtain a concrete description of simplicial sets of dimension $\leq 1$ (Proposition 1.1.6.9).
Definition 1.1.6.1. A directed graph $G$ consists of the following data:
A set $\operatorname{Vert}(G)$, whose elements we refer to as vertices of $G$.
A set $\operatorname{Edge}(G)$, whose elements we refer to as edges of $G$.
A pair of functions $s,t: \operatorname{Edge}(G) \rightarrow \operatorname{Vert}(G)$ which assign to each edge $e \in \operatorname{Edge}(G)$ a pair of vertices $s(e)$, $t(e) \in \operatorname{Vert}(G)$ that we refer to as the source and target of $e$, respectively.
Warning 1.1.6.2. The terminology of Definition 1.1.6.1 is not standard. Note that a directed graph $G$ can have distinct edges $e \neq e'$ having the same source $s(e) = s(e')$ and target $t(e) = t(e')$ (for this reason, directed graphs in the sense of Definition 1.1.6.1 are sometimes called multigraphs). Definition 1.1.6.1 also allows graphs which contain loops: that is, edges $e$ satisfying $s(e) = t(e)$.
Remark 1.1.6.3. It will sometimes be convenient to represent a directed graph $G$ by a diagram, having a node for each vertex $v$ of $G$ and an arrow for each edge $e$ of $G$, directed from the source of $e$ to the target of $e$. For example, the diagram represents a directed graph with three vertices and five edges.
\[ \xymatrix@R =50pt@C=50pt{ & \bullet \ar@ /^2pc/[dr] \ar [dr] & \\ \bullet \ar@ /^1.5pc/[rr] \ar [ur] & & \bullet \ar [ll] } \]
Example 1.1.6.4. To every simplicial set $X$, we can associate a directed graph $\mathrm{Gr}( X)$ as follows:
The vertex set $\operatorname{Vert}( \mathrm{Gr}(X) )$ is the set of $0$-simplices of the simplicial set $X$.
The edge set $\operatorname{Edge}( \mathrm{Gr}(X) )$ is the set of nondegenerate $1$-simplices of the simplicial set $X$.
For every edge $e \in \operatorname{Edge}( \mathrm{Gr}(X) )$, the source $s(e)$ is the vertex $d^{1}_1(e)$, and the target $t(e)$ is the vertex $d^{1}_0(e)$ (here $d^{1}_0$ and $d^{1}_1$ denote the face operators of Construction 1.1.1.4).
It will be convenient to construe Example 1.1.6.4 as providing a functor from the category of simplicial sets to the category of directed graphs. First, we need an appropriate definition for the latter category.
Definition 1.1.6.5. Let $G$ and $G'$ be directed graphs (in the sense of Definition 1.1.6.1). A morphism from $G$ to $G'$ is a function $f: \operatorname{Vert}( G ) \amalg \operatorname{Edge}(G) \rightarrow \operatorname{Vert}(G') \amalg \operatorname{Edge}(G')$ which satisfies the following conditions:
For each vertex $v \in \operatorname{Vert}(G)$, the image $f(v)$ belongs to $\operatorname{Vert}(G')$.
Let $e \in \operatorname{Edge}(G)$ be an edge of $G$ with source $v = s(e)$ and target $w = t(e)$. Then exactly one of the following conditions holds:
The image $f(e)$ is an edge of $G'$ having source $s( f(e) ) = f(v)$ and target $t( f(e) ) = f(w)$.
The image $f(e)$ is a vertex of $G'$ satisfying $f(v) = f(e) = f(w)$.
We let $\operatorname{Graph}$ denote the category whose objects are directed graphs and whose morphisms are morphisms of directed graphs (with composition defined in the evident way).
Warning 1.1.6.6. Note that part $(b)$ of Definition 1.1.6.5 allows the possibility that a morphism of directed graphs $G \rightarrow G'$ can “collapse” edges of $G$ to vertices of $G'$. Many other notions of morphism between (directed) graphs appear in the literature; we single out Definition 1.1.6.5 because of its close connection with the theory of simplicial sets (see Proposition 1.1.6.7 below).
Let $X = X_{\bullet }$ be a simplicial set and let $\mathrm{Gr}( X )$ be the directed graph of Example 1.1.6.4. Then the disjoint union $\operatorname{Vert}( \mathrm{Gr}(X) ) \amalg \operatorname{Edge}( \mathrm{Gr}( X ) )$ can be identified with the set $X_1$ of all $1$-simplices of $X$ (by identifying each vertex $x \in X$ with the degenerate edge $\operatorname{id}_{x}$).
Proposition 1.1.6.7. Let $X =X_{\bullet }$ and $Y = Y_{\bullet }$ be simplicial sets, and let $f: X \rightarrow Y$ be a morphism of simplicial sets. Then the induced map is a morphism of directed graphs from $\mathrm{Gr}( X )$ to $\mathrm{Gr}( Y)$, in the sense of Definition 1.1.6.5.
\[ \operatorname{Vert}( \mathrm{Gr}(X) ) \amalg \operatorname{Edge}( \mathrm{Gr}(X) ) \simeq X_1 \xrightarrow {f} Y_1 \simeq \operatorname{Vert}( \mathrm{Gr}(Y) ) \amalg \operatorname{Edge}( \mathrm{Gr}(Y) ) \]
Proof. Since $f$ commutes with the degeneracy operator $s^{0}_0$, it carries degenerate $1$-simplices of $X$ to degenerate $1$-simplices of $Y$, and therefore satisfies requirement $(a)$ of Definition 1.1.6.5. Requirement $(b)$ follows from the fact that $f$ commutes with the face operators $d^{1}_0$ and $d^{1}_1$. $\square$
It follows from Proposition 1.1.6.7 that we can regard the construction $X \mapsto \mathrm{Gr}( X )$ as a functor from the category $\operatorname{Set_{\Delta }}$ of simplicial sets to the category $\operatorname{Graph}$ of directed graphs.
Proposition 1.1.6.8. Let $X$ and $Y$ be simplicial sets. If $X$ has dimension $\leq 1$, then the canonical map is bijective.
\[ \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X, Y ) \rightarrow \operatorname{Hom}_{ \operatorname{Graph}}( \mathrm{Gr}( X), \mathrm{Gr}( Y) ) \]
Proof. Set $G = \mathrm{Gr}(X)$. If $X$ has dimension $\leq 1$, then Proposition 1.1.4.12 supplies a pushout diagram
It follows that, for any simplicial set $Y = Y_{\bullet }$, we can identify $\operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X, Y )$ with the fiber product
which parametrizes morphisms of directed graphs from $\mathrm{Gr}( X )$ to $\mathrm{Gr}( Y )$. $\square$
It follows from Proposition 1.1.6.8 that the theory of simplicial sets of dimension $\leq 1$ is essentially equivalent to the theory of directed graphs.
Proposition 1.1.6.9. Let $\operatorname{Set_{\Delta }}$ denote the category of simplicial sets and let $\operatorname{Set}_{\Delta }^{\leq 1} \subseteq \operatorname{Set_{\Delta }}$ denote the full subcategory spanned by the simplicial sets of dimension $\leq 1$. Then the construction $X \mapsto \mathrm{Gr}( X )$ induces an equivalence of categories $\operatorname{Set}_{\Delta }^{\leq 1} \rightarrow \operatorname{Graph}$.
Proof. It follows from Proposition 1.1.6.8 that the functor $X \mapsto \mathrm{Gr}(X )$ is fully faithful when restricted to simplicial sets of dimension $\leq 1$. It will therefore suffice to show that it is essentially surjective. Let $G$ be any directed graph, and form a pushout diagram of simplicial sets
Then $X$ is a simplicial set of dimension $\leq 1$ (Proposition 1.1.3.11), and the directed graph $\mathrm{Gr}( X)$ is isomorphic to $G$. $\square$
Remark 1.1.6.10. The proof of Proposition 1.1.6.9 gives an explicit description of the inverse equivalence $\operatorname{Graph}\simeq \operatorname{\mathcal{C}}\hookrightarrow \operatorname{Set_{\Delta }}$: it carries a directed graph $G$ to the $1$-dimensional simplicial set $G_{\bullet }$ given by the colimit of the diagram
\[ ( \underset { v \in \operatorname{Vert}( G )}{\coprod } \Delta ^0 ) \leftarrow (\underset { e \in \operatorname{Edge}( G )}{\coprod } \operatorname{\partial \Delta }^{1} ) \rightarrow ( \underset { e \in \operatorname{Edge}( G)}{\coprod } \Delta ^{1} ). \]
Example 1.1.6.11. Let $G$ be a directed graph and let $G_{\bullet }$ denote the associated simplicial set of dimension $\leq 1$ (Remark 1.1.6.10). Then $G_{\bullet }$ has dimension $\leq 0$ if and only if the edge set $\operatorname{Edge}(G)$ is empty. In this case, $G_{\bullet }$ can be identified with the constant simplicial set $\underline{\operatorname{Vert}(G)}$.