This question is taken from Category Theory for Programmers by Bartosz Milewski (1.6).

Q: When is a directed graph a category?

My intuition is that for a directed graph $G$ to have category structure, the existence of edges (arrows) $A \rightarrow B$ and $B \rightarrow C$ would imply the existence of the edge/arrow $A \rightarrow C$. I'm not quite sure if that point is correct, or if the meaning is something weaker like $A \rightarrow B \rightarrow C\rightarrow D, D \rightarrow B \implies D \rightarrow C$

Assuming the stronger condition, That would imply that any pair of connected vertices must have an arrow directly linking them, which would imply that $G$, viewed as an undirected graph, would have the same connectivity as a graph made of complete graphs with some overlapping vertices. More precisely, any connected subgraph $H \subset G$, $|H| = n$, when viewed as an undirected graph, must have $ H \cong K_n$. Can something stronger be said?

  • 1
    $\begingroup$ A graph is a category iff it is reflexive and transitive. In other words, the relations which form a category are exactly the preorders. $\endgroup$ Nov 9, 2021 at 21:01
  • $\begingroup$ That whenever you have a directed edge from A to B and one from B to C you also have a directed edge from A to C is called "transitivity". You also need something to play the role of identity arrows. $\endgroup$ Nov 9, 2021 at 21:02
  • $\begingroup$ Got it, so there need to be "self-loops" to each vertex representing the identity. And transitivity $A \rightarrow B \rightarrow C \implies A \rightarrow C$ is the other necessary condition for a directed graph to be a category. $\endgroup$
    – Michael K
    Nov 9, 2021 at 21:08
  • 1
    $\begingroup$ A directed graph is a category when we equip it with a category structure (by specific compositions and identity loops). I guess you mean when a directed graph is the underlying graph of a category. $\endgroup$
    – Berci
    Nov 9, 2021 at 21:55


You must log in to answer this question.

Browse other questions tagged .