# When is a directed graph a category?

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?

• A graph is a category iff it is reflexive and transitive. In other words, the relations which form a category are exactly the preorders. Nov 9, 2021 at 21:01
• 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. Nov 9, 2021 at 21:02
• 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. Nov 9, 2021 at 21:08
• 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. Nov 9, 2021 at 21:55