A little bit of background: A graph G is, of course, a set of vertices V(G) and a multiset of edges, which are unordered pairs of (not necessarily distinct) vertices. We say that two vertices v\_1, v\_2 are adjacent if {v\_1, v\_2} is an edge. A directed graph, or digraph is essentially the same thing, except that the edges are now ordered pairs. Digraphs have a rather nice categorical interpretation.


A *graph homomorphism* is exactly what it should be, categorically, if you think of graphs as "sets with an adjacency structure." It's a map f: V(G) \rightarrow V(H) is a homomorphism if v\_1, v\_2 \in V(G) adjacent implies f(v\_1), f(v\_2) adjacent. The notion of homomorphism for directed graphs is essentially the same; if there's an edge from v\_1 to v\_2, then there's an edge from f(v\_1) to f(v\_2). Taking these definitions as morphisms, we can define categories of graphs and of digraphs. 


Oftentimes in graph theory (particularly when linear algebra methods come into play), it's easier to work with a digraph than a graph, and so we usually orient the edges arbitrarily. But this isn't really natural...


There's a forgetful functor from the category of digraphs to the category of graphs. Does this functor have an adjoint? (I forget which is left and which is right.) Now that I think about it, is the obvious thing (replace each edge by a pair of directed edges, one in each direction) an adjoint, and if so is there a way to fudge the categories so that simple graphs are taken to simple digraphs?



Is there a free digraph associated to a graph?
I like to use the following definitions, which give a nonstandard definition of undirected graph but produce particularly nice categories.



> 
> A directed graph is a pair of sets V and E together with two maps s, t : E -> V. Call the category of these DirGraph.
> 
> 
> An undirected graph is a pair of sets V and E together with two maps s, t : E -> V plus a map r : E -> E such that r^2 = 1, sr = t and tr = s. Call the category of these UndirGraph.
> 
> 
> 


The interpretation of directed graphs should be obvious. For an undirected graph, an edge is an orbit under r of an element of E. Note that there are two kinds of loops--orbits of size 1 or 2.


We can represent the categories of directed graphs and undirected graphs as the categories of presheaves on two categories Dir and Undir respectively (each has two objects corresponding to V and E and a small number of morphisms). There's an inclusion functor i : Dir -> Undir which induces a restriction functor UndirGraph -> DirGraph; this is your doubling functor. It has adjoints on both sides (left and right Kan extension). The left adjoint is your "forgetful" functor DirGraph -> UndirGraph. The right adjoint is another functor DirGraph -> UndirGraph which roughly speaking sends a directed graph G to the undirected graph G' with the same vertices where an edge between v and w in G' is a pair of an edges in G, one from v to w and one from w to v.


So with these definitions, not only does the "forgetful" functor have a right adjoint, but its right adjoint also has a right adjoint.


