# Does the forgetful functor $U: \mathbf{Gph} \to \mathbf{Set}$ have a left adjoint?

Often forgetful functors from a category $$\mathbf{C}$$ of algebraic objects to $$\mathbf{Set}$$ have a left adjoint, which gives a "free construction" of a $$\mathbf{C}$$-object on any set $$X$$.

What about the forgetful functor from the category of simple graphs $$\mathbf{Gph}$$ - does this have a left adjoint? This would presumably give a construction of a "free graph" on a set.

Are there any other categories of "relational structures" (e.g. posets, directed graphs) where the forgetful functor has a left adjoint?

• Which forgetful functor do you have in mind? There are a couple of different natural functors from $\mathbf{Grph}$ to $\mathbf{Set}$. Mar 14 '20 at 7:28
• Any one, but the one I had in mind was the one assigning a graph its underlying vertex set. Mar 14 '20 at 7:31
• I'm pretty sure a left adjoint to that one is just the functor taking a set $X$ to the graph with vertex set $X$ and no edges. I can't recall if the connected components functor on simple graphs has a left adjoint, though... Mar 14 '20 at 7:48

We need to be a bit more precise here, and specify what the arrows are in $$\mathbf{Gph}$$. A natural choice would be maps $$f: G \to G'$$ between the vertex sets such that if there is an edge between $$x,y \in G$$ (which I will denote by $$E(x, y)$$), then there is an edge between $$f(x)$$ and $$f(y)$$. In this case the forgetful functor $$U: \mathbf{Gph} \to \mathbf{Set}$$, which sends a graph to its underlying vertex set, does indeed have a left adjoint.
The construction was already mentioned by Malice Vidrine in the comments. We can define $$F: \mathbf{Set} \to \mathbf{Gph}$$ by sending a set $$X$$ to the graph $$F(X)$$ with vertex set $$X$$ and no edges. A function $$f: X \to Y$$ of sets is then also an arrow $$f: F(X) \to F(Y)$$ in $$\mathbf{Gph}$$, so we just set $$F(f) = f$$.
Let $$X$$ be a set and $$G$$ be a graph. Then a function $$X \to U(G)$$ is literally the same thing as a morphism of graphs $$F(X) \to G$$. So $$\operatorname{Hom}(X, U(G)) = \operatorname{Hom}(F(X), G)$$, which is definitely natural, so $$F$$ is left adjoint to $$G$$.
In fact, $$F: \mathbf{Set} \to \mathbf{Gph}$$ itself has again a left adjoint $$C: \mathbf{Gph} \to \mathbf{Set}$$. Here $$C$$ is the connected components functor. So it takes a graph $$G$$ to the set of connected components of $$G$$. It is a good exercise to define $$C$$ on the arrows in $$\mathbf{Gph}$$ and to check that it is indeed left adjoint to $$F$$.