# What is the free category on the underlying graph of a category?

Let $\mathcal{D}$ be a category. Ittay Weiss wrote about Free($\mathcal{D}$) in chat with me. He said Free($\mathcal{D}$) is the free category on the underlying graph of $\mathcal{D}$. Is Free($\mathcal{D}$) different from $\mathcal{D}$? I would like to know the exact definition of Free($\mathcal{D}$) and applications of the notion.

EDIT(Jan. 14, 2013) Is Free($\mathcal{D}$) isomorphic or equivalent to $\mathcal{D}$? Counterexamples?

-
There is a forgetful functor from the category of categories to the category of (directed multi)graphs. The free functor is the left adjoint. The explicit construction is more-or-less what you expect: it has morphisms for each generating edge, as well as all formal compositions of such. – Zhen Lin Jan 13 '13 at 18:50
Almost always. For example, the free category on the empty graph is the empty category; but as soon as there are two composable arrows then the free category is different. – Zhen Lin Jan 13 '13 at 19:23
@ZhenLin Actually, if I understand correctly, the question is: is $Free(U(\mathcal{D}))$ different from $\mathcal{D}$, where $\mathcal{D}$ is a category and U is the forgetful functor $U:Cat \to Graph$ – magma Jan 13 '13 at 20:37
Suppose given a pair of morphisms $f, g$ with composite $h=g\circ f$. Then in the free category has morphisms $f,g,h$ as well, but now $h\ne g\circ f$. – Zhen Lin Jan 13 '13 at 20:59
@Zhen: Wrong side of the adjunction: with the symbols defined in the OP, we get the counit map $\text{Free}(\mathcal{D}) \to \mathcal{D}$ given by multiplying a formal product. – Hurkyl Jan 15 '13 at 1:24

For a graph $G$ with object set $O$ let $C=FG$ be the category with the same objects and whose arrows from $a$ to $b$ are strings $$a=a_1\stackrel{f_1}⟶a_2\stackrel{f_2}⟶...\stackrel{f_{n-1}}⟶a_n=b$$ of length $n-1$. We define the composition of two strings by juxtaposition, where the lengths are added. This is by its very nature associative. A string of length $0$ is thus the identity. Let's write such strings as $(a_1,f_1,f_2,...,f_{n-1},a_n)$. It can be decomposed as $(a_{n-1},f_{n-1},a_n)∘...∘(a_1,f_1,a_2)$. Let $η:G→UC$ be the graph map sending $f:a→b$ to $(a,f,b)$.
Now, consider any graph map $g:G→UB$ for a category $B$. Using the decomposition of a string of length $n$ into strings of length $1$, it is easy to see that there is a unique functor $g':C→B$ such that $Ug'∘η=g$. Hence $η$ is universal from $G$ to $U$. The object function $F$ can then be made into a free functor $\mathbf{Grph}\to\mathbf{Cat}$.
The category on one object with only the identity morphism has as underlying graph a single vertex with a loop. The free category on the single vertex with a loop is the category on one object with countably many non-identity arrows $a,a\circ a,...$ i.e. as a monoid it is $\mathbb{N}$. The counit functor, of course, just sends all these arrows to the identity. The possibly-subtle point is that these non-identity arrows $a$ are generated by an arrow that was the identity before we applied the forgetful functor. But this is necessary because not every node in every graph has a distinguished loop to map to the identity in generating a free category.