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?
Best Answer
Whenever I say graph in this answer, I mean simple graph.
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$.