Re: Undirected graphs

[Vaughan Pratt <pratt@cs.stanford.edu>]

My definition of 2-UGraph (undirected graphs with at most one edge from
any given vertex to another) 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" was an
attempt to say "2-UGraph is a retract of Set-UGraph" with both too few
words and too many.

2-UGraph is the full subcategory of Set-UGraph consisting of graphs with
at most one edge per "homset", and at the same time the quotient of
Set-UGraph arising from identifying all members of each homset of each
graph.  I.e. a retract.

This is something of an eye-opener for me as I have for decades thought
of the undirected graph (of the one-edge-per-homset kind) as the
algebraically impoverished cousin of the directed graph.  I am tickled
pink to find it arising as a retract of a presheaf category, and
moreover without either of the two quirks that have been pointed out for
the more general undirected graphs allowing multiple edges per homset
(Set-UGraph has two types of distinguished loop, and does not embed in
Set-DGraph).

Vaughan Pratt