### 1.1.5 Directed Graphs as Simplicial Sets

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)$.

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:

- $(a)$
For each vertex $v \in \operatorname{Vert}(G)$, the image $f(v)$ belongs to $\operatorname{Vert}(G')$.

- $(b)$
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:

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

\[ \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 }) ) \]

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.

**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

\[ \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X_{\bullet }, Y_{\bullet } ) \rightarrow \operatorname{Hom}_{ \operatorname{Graph}}( \mathrm{Gr}( X_{\bullet }), \mathrm{Gr}( Y_{\bullet } ) ) \]

is bijective.

**Proof.**
If $X_{\bullet }$ has dimension $\leq 1$, then Proposition 1.1.3.13 provides a pushout diagram

\[ \xymatrix { \underset { e \in \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) )}{\coprod } \operatorname{\partial \Delta }^{1} \ar [r] \ar [d] & \underset { e \in \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) )}{\coprod } \Delta ^{1} \ar [d] \\ \underset { v \in \operatorname{Vert}( \mathrm{Gr}(X_{\bullet }) )}{\coprod } \Delta ^0 \ar [r] & X_{\bullet }. } \]

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

\[ ( \underset { e \in \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) )}{\prod } Y_1) \underset { \prod _{ e \in \operatorname{Edge}( \mathrm{Gr}(X_{\bullet }) )} (Y_0 \times Y_0) }{\times } (\underset { v \in \operatorname{Vert}( \mathrm{Gr}(X_{\bullet }) )}{\prod } Y_0), \]

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 is essentially surjective. Let $G$ be any directed graph, and form a pushout diagram of simplicial sets

\[ \xymatrix { \underset { e \in \operatorname{Edge}( G )}{\coprod } \operatorname{\partial \Delta }^{1} \ar [r] \ar [d]^{(s,t)} & \underset { e \in \operatorname{Edge}( G)}{\coprod } \Delta ^{1} \ar [d] \\ \underset { v \in \operatorname{Vert}( G )}{\coprod } \Delta ^{0} \ar [r] & X_{\bullet }. } \]

Then $X_{\bullet }$ is a simplicial set of dimension $\leq 1$, and the directed graph $\mathrm{Gr}( X_{\bullet } )$ is isomorphic to $G$.
$\square$

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)$.