# Is there any nontrivial monad on the category of graphs?

The question is in the title, but let me specify what I mean by the category of graphs.

In the context of this question, the category of graphs is the category of symmetric irreflexive relations. That means, not the category of symmetric reflexive relations. That means, no loops and at most one edge between vertices.

-
And what do you mean by a nontrivial monad? Wouldn't operads be a source of examples? – David White Apr 18 '13 at 11:58
A trivial monad for a category $C$ is the one that arises from the adjoint pair of functors $(1_C,1_C)$. I do not understand what you mean by your second question. – Gejza Jenča Apr 18 '13 at 12:07

I take it morphisms $f: X \to Y$ are by definition functions that preserve the relation: if $x, x'$ are related in $X$, then $f(x), f(x')$ are related in $Y$.

It's easy to manufacture some silly examples of nontrivial monads, by finding suitable monoidal products on the category of graphs and then finding monoids with respect to that monoidal product. One such monoidal product takes the disjoint sum of two graphs. Then an example of a monoid therein is the one-point graph $1$, which carries a unique monoid structure.

The associated monad $M$ takes a graph and adjoins an isolated point to the graph, which one could regard as basepoint. If $f: X \to Y$ is a graph morphism, then $M(f)$ is the obvious basepoint preserving extension. To be precise, $M(X) = 1 + X$; the unit of the monad is the inclusion of $X$ in $1 + X$, and the multiplication $1 + 1 + X \to 1 + X$ is the identity on $X$ but identifies the two copies of $1$ as one.

-
I know that I am an not good at making examples but I do not understand how I could miss this one. – Gejza Jenča Apr 18 '13 at 20:19
Don't worry; it took me a couple of minutes to think of this (having thought of and then discarding things like the complete graph which doesn't work). More important maybe is the general technique of using monoids in monoidal categories to cook up examples of monads. – Todd Trimble Apr 18 '13 at 21:22

There are billions and billions of them. But it turns out I originally suggested two non-examples:

• The non-monad which takes a graph and turns it into the complete graph on the same vertices.
• The comonad which takes a graph and turns it into the discrete graph on the same vertices. (This example was edited after Andreas Blass made his comment.)

And two that still seem to be examples:

• The monad which takes a graph and creates a new one with the same vertices, but connects two vertices iff there is a path between them in the original graph.
• The monad arising from $\pi_0$: it takes a graph and returns the discrete graph whose vertices are the connected components of the original graph.
-
In the second example, the discrete graph on the same vertices, what is the unit of the monad? – Andreas Blass Apr 18 '13 at 12:41
I'm not sure the complete graph example works. If you apply such a completion functor to the function $2 \to 1$ from the 2-element set to the 1-element set (with the discrete graph structures), where would the edge in the completion of $2$ go to? – Todd Trimble Apr 18 '13 at 13:34
Please, do not delete the answer. The last example is correct,I think. – Gejza Jenča Apr 19 '13 at 6:43
In the currently last example, sending $G$ to the discrete graph on $\pi_0(G)$, isn’t there a problem with the unit morphism — edges within each connected component have no edges to map to? – Peter LeFanu Lumsdaine Apr 28 '13 at 3:25
I think this proves I am very smart. Had I been doing things randomly, at least some of these would be actual examples. It takes a special talent to produce four plausibly-sounding non-examples. – Andrej Bauer Apr 28 '13 at 13:53