My background is in group theory and algebraic geometry. I am due to give an introduction to the topos of graphs to some graph theorists. I understand the material, but what I am missing is some sort of motivating example, i.e. some statement that can be proven using category theory (I'm also fine with type theory or whatever), but that can be understood using only graph theory.

To be clear, I am not necessarily looking for a result that can only be proven using category theory. Saying "hey, you know this result from your field? Here's an alternative proof" would do just fine as a motivation.

Bonus points if the proof is low-level enough that I can actually include it in my presentation and/or if the result is well-known and/or actually useful.

I am grateful for any suggestions!

  • $\begingroup$ You could show that graphs are the backbone of categories; ie every category is formed from the free paths category on a graph /with/ additional identifications. This is like how every monoid is made from free words, lists, with additional identifications. See alhassy.github.io/PathCat $\endgroup$ May 7, 2020 at 15:30
  • $\begingroup$ As a side note, if you're working in a topos of graphs, you're not talking about simple graphs. The topos of functors to sets from the diagram category $\bullet \rightrightarrows \bullet$ is the category of directed graphs allowing multiple edges and loops. $\endgroup$ May 7, 2020 at 16:03
  • $\begingroup$ @KevinArlin True, that's why I put the (simple) in parentheses. I don't actually care which category of graphs my example uses. $\endgroup$ May 7, 2020 at 16:16
  • $\begingroup$ @BettaGeorge Ah, got it. $\endgroup$ May 7, 2020 at 16:43
  • 2
    $\begingroup$ This may not be quite what you're looking for, but Joyal's proof of Cayley's formula is a beautiful category-theoretic proof of a graph-theoretic statement. $\endgroup$
    – varkor
    May 7, 2020 at 16:58


You must log in to answer this question.