Let me define undirected graphs - slightly deviating from common usage - not to be a symmetric binary relation on an *arbitrary finite* set, but on a *finite subset of* $\,\mathbb{N}$. Anyway I write $G = (V(G), E(G))$ where $V(G)\subset \mathbb{N}$ is the underlying set of vertices of the graph $G$ and $E(G)$ is its set of unordered pairs of vertices called edges.

There are - among others - two notions of morphisms for a category of undirected graphs: **graph homomorphisms** (the weaker notion, giving rise to the category $\mathcal{G}_1$) and **elementary embeddings** (the stronger notion, giving rise to the category $\mathcal{G}_2$, which is a subcategory of $\mathcal{G}_1$).

For each **permutation** $\pi: \mathbb{N} \rightarrow \mathbb{N}$ there are (endo-)functors $F_\pi$ both from $\mathcal{G}_1$ to itself and from $\mathcal{G}_2$ to itself which are definable in an obvious way:

$$V(F_\pi(G)) = \pi(V(G))$$ $$\lbrace x,y\rbrace \in E(F_\pi(G))\quad \text{iff}\quad \lbrace \pi^{-1}(x),\pi^{-1}(y) \rbrace \in E(G)$$ $$F_\pi(f) = F_{\pi} \circ f \circ F_{\pi^{-1}}$$

[Intermediate questions]

1. Is it OK to write the definition of $F_\pi(f)$ like this?

2. Can $F_\pi$ - thus defined - be also a (somehow forgetful) functor from $\mathcal{G}_2$ to $\mathcal{G}_1$, but eventually not the other way around?

Only for $\mathcal{G}_2$ - i.e. for elementary embeddings as morphisms - there is (as I do believe) another "uniform" family of (endo-)functors from $\mathcal{G}_2$ to itself. Consider formulas $\phi(x,y)$ of the first-order language with signature $\sigma = \lbrace E\,\rbrace$ with the binary relation symbol $E(x,y)$ indicating that $\lbrace x,y\rbrace \in E(G)$. For each such **formula** $\phi$ there is a "definition functor" $F_\phi$ definable like this:

$$V(F_\phi(G)) = V(G)$$ $$\lbrace x,y\rbrace \in E(F_\phi(G))\quad \text{iff}\quad G \models \phi(x,y)$$ $$F_\phi(f) = f$$

$f$ has to be seen as a map on the vertex set only, otherwise the functor condition $\operatorname{src}(F(f)) = F(\operatorname{src}(f))$ would not be fulfilled, because $F_\phi(G)$ is another graph than $G$ (having the same vertex set only).

[Intermediate question]Are these "definition functors" $F_\phi$ really functors?

Assuming the latter, I have a bunch of questions (some more trivial than others, but I'd like to ask them all, because they belong together):

Given a "permutation functor" $F_\pi$: for which functors $F$ are there natural transformations $\eta$ from $F_\pi$ to $F$ (and vice versa)? Do these functors $F$ have to be permutation functors themselves? If so: for which permutations $\pi'$ are there natural transformations $\eta$ from $F_\pi$ to $F_{\pi'}$ (and vice versa)?

The same for "definition functors": Given a definition functor $F_\phi$: for which functors $F$ are there natural transformations $\eta$ from $F_\phi$ to $F$ (and vice versa)? Do these functors $F$ have to be definition functors themselves? If so: for which formulas $\phi'$ are there natural transformations $\eta$ from $F_\phi$ to $F_{\phi'}$ (and vice versa)?

What are examples of endo-functors of $\mathcal{G}_2$ that are not finite combinations of permutation and definition functors?