We now generalize Proposition 1.1.4.13 to obtain a concrete description of simplicial sets having dimension $\leq 1$ (Proposition 1.1.5.9).
Definition 1.1.5.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.5.2. The terminology of Definition 1.1.5.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.5.1 are sometimes called multigraphs). Definition 1.1.5.1 also allows graphs which contain loops: that is, edges $e$ satisfying $s(e) = t(e)$.
Remark 1.1.5.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.5.4. To every simplicial set $X_{\bullet }$, we can associate a directed graph $\mathrm{Gr}( X_{\bullet } )$ as follows:
The vertex set $\operatorname{Vert}( \mathrm{Gr}(X_{\bullet } ) )$ is the set of $0$-simplices of the simplicial set $X_{\bullet }$.
The edge set $\operatorname{Edge}( \mathrm{Gr}(X_{\bullet } ) )$ is the set of nondegenerate $1$-simplices of the simplicial set $X_{\bullet }$.
For every edge $e \in \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) ) \subseteq X_1$, the source $s(e)$ is the vertex $d_1(e)$, and the target $t(e)$ is the vertex $d_0(e)$ (here $d_0, d_1: X_1 \rightarrow X_0$ are the face maps of Notation 1.1.1.8).
It will be convenient to construe Example 1.1.5.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.5.5. Let $G$ and $G'$ be directed graphs (in the sense of Definition 1.1.5.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.5.6. Note that part $(b)$ of Definition 1.1.5.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.5.5 because of its close connection with the theory of simplicial sets (see Proposition 1.1.5.7 below).
Let $X_{\bullet }$ be a simplicial set and let $\mathrm{Gr}( X_{\bullet } )$ be the directed graph of Example 1.1.5.4. Then the disjoint union $\operatorname{Vert}( \mathrm{Gr}(X_{\bullet }) ) \amalg \operatorname{Edge}( \mathrm{Gr}( X_{\bullet } ) )$ can be identified with the set $X_1$ of all $1$-simplices of $X_{\bullet }$ (where we identify $\operatorname{Vert}( \mathrm{Gr}(X_{\bullet } ) )$ with the collection of degenerate $1$-simplices via the degeneracy map $s_0: X_0 \rightarrow X_1$).
Proposition 1.1.5.7. Let $f: X_{\bullet } \rightarrow Y_{\bullet }$ be a map of simplicial sets. Then the induced map is a morphism of directed graphs from $\mathrm{Gr}( X_{\bullet } )$ to $\mathrm{Gr}( Y_{\bullet } )$, in the sense of Definition 1.1.5.5.
\[ \operatorname{Vert}( \mathrm{Gr}(X_{\bullet }) ) \amalg \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) ) \simeq X_1 \xrightarrow {f} Y_1 \simeq \operatorname{Vert}( \mathrm{Gr}(Y_{\bullet } ) ) \amalg \operatorname{Edge}( \mathrm{Gr}(Y_{\bullet }) ) \]
Proof. Since $f$ commutes with the degeneracy operator $s_0$, it carries degenerate $1$-simplices of $X_{\bullet }$ to degenerate $1$-simplices of $Y_{\bullet }$, and therefore satisfies requirement $(a)$ of Definition 1.1.5.5. Requirement $(b)$ follows from the fact that $f$ commutes with the face operators $d_0$ and $d_1$. $\square$
It follows from Proposition 1.1.5.7 that we can regard the construction $X_{\bullet } \mapsto \mathrm{Gr}( X_{\bullet } )$ as a functor from the category $\operatorname{Set_{\Delta }}$ of simplicial sets to the category $\operatorname{Graph}$ of directed graphs.
Proposition 1.1.5.8. Let $X_{\bullet }$ and $Y_{\bullet }$ be simplicial sets. If $X_{\bullet }$ has dimension $\leq 1$, then the canonical map is bijective.
\[ \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X_{\bullet }, Y_{\bullet } ) \rightarrow \operatorname{Hom}_{ \operatorname{Graph}}( \mathrm{Gr}( X_{\bullet }), \mathrm{Gr}( Y_{\bullet } ) ) \]
Proof. If $X_{\bullet }$ has dimension $\leq 1$, then Proposition 1.1.3.13 provides a pushout diagram
It follows that, for any simplicial set $Y_{\bullet }$, we can identify $\operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X_{\bullet }, Y_{\bullet } )$ with the fiber product
which is precisely the set of morphisms of directed graphs from $\mathrm{Gr}( X_{\bullet } )$ to $\mathrm{Gr}( Y_{\bullet } )$. $\square$
It follows from Proposition 1.1.5.8 that the theory of simplicial sets of dimension $\leq 1$ is essentially equivalent to the theory of directed graphs.
Proposition 1.1.5.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_{\bullet } \mapsto \mathrm{Gr}( X_{\bullet } )$ induces an equivalence of categories $\operatorname{Set}_{\Delta }^{\leq 1} \rightarrow \operatorname{Graph}$.
Proof. It follows from Proposition 1.1.5.8 that the functor $X_{\bullet } \mapsto \mathrm{Gr}(X_{\bullet } )$ 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_{\bullet }$ is a simplicial set of dimension $\leq 1$, and the directed graph $\mathrm{Gr}( X_{\bullet } )$ is isomorphic to $G$. $\square$
Remark 1.1.5.10. The proof of Proposition 1.1.5.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 pushout
\[ ( \underset { v \in \operatorname{Vert}( G )}{\coprod } \Delta ^0 ) \amalg _{ \underset { e \in \operatorname{Edge}( G )}{\coprod } \operatorname{\partial \Delta }^{1} } ( \underset { e \in \operatorname{Edge}( G)}{\coprod } \Delta ^{1} ). \]
Example 1.1.5.11. Let $G$ be a directed graph and let $G_{\bullet }$ denote the associated simplicial set of dimension $\leq 1$ (Remark 1.1.5.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 associated to the vertex set $\operatorname{Vert}(G)$.