### 1.1.6 Directed Graphs as Simplicial Sets

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

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:

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

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

is a morphism of directed graphs from $\mathrm{Gr}( X )$ to $\mathrm{Gr}( Y)$, in the sense of Definition 1.1.6.5.

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

\[ \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X, Y ) \rightarrow \operatorname{Hom}_{ \operatorname{Graph}}( \mathrm{Gr}( X), \mathrm{Gr}( Y) ) \]

is bijective.

**Proof.**
Set $G = \mathrm{Gr}(X)$. If $X$ has dimension $\leq 1$, then Proposition 1.1.4.12 supplies a pushout diagram

\[ \xymatrix@R =50pt@C=50pt{ \underset { e \in \operatorname{Edge}(G )}{\coprod } \operatorname{\partial \Delta }^{1} \ar [r] \ar [d] & \underset { e \in \operatorname{Edge}(G)}{\coprod } \Delta ^{1} \ar [d] \\ \underline{ \operatorname{Vert}(G) } \ar [r] & X. } \]

It follows that, for any simplicial set $Y = Y_{\bullet }$, we can identify $\operatorname{Hom}_{\operatorname{Set_{\Delta }}}( X, Y )$ with the fiber product

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

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

\[ \xymatrix@R =50pt@C=50pt{ \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. } \]

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$

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