Sebastiano Vigna wrote on 3/8/06:
The problem is that the standard representation for undirected graphs (subsets of unordered pairs) fails to distinguish between the two kind of loops. The presheaf representation makes this distinction clear.
I wouldn't call this a "failure" of the set-of-unordered-pairs notion of undirected graph, which should be understood in 2-enriched (2 = 0->1) terms rather than Set-enriched. In my March 1 post I distinguished the "set-enriched" or presheaf graph categories Set-DGraph and Set-UGraph from the "2-enriched" graph categories 2-DGraph and 2-UGraph ("homsets" of edges are either 0 or 1, i.e. empty or singleton), pointing out that 2-UGraph was a full subcategory of 2-DGraph but Set-UGraph was not a full subcategory of 2-DGraph, via the same mechanism that creates two kinds of loops in Set-UGraph. There is only one kind of loop in 2-UGraph, which category theory is faithful to when this kind of undirected graph is properly described in categorical language. One description would be as the full subcategory of Set-UGraph (= Set^M^op for M the monoid Set(2,2)) induced by the evident functor Nonempty:Set->2 collapsing nonempty homsets to singletons; it would be nice if 2-UGraph arose more naturally, e.g. as some sort of 2-enriched presheaf category, though I don't see how. Vaughan Pratt