Let $V$ be a set and let $V^V$ denote the set of all functions $f:V\to V$. Suppose that $F\subseteq V^V$. Let $[V]^2 = \big\{\{x,y\}: x, y\in V \land x\neq y\big\}$. We say $E\subseteq [V]^2$ is *$F$-compatible* if all members of $F$ are [graph homomorphisms](https://en.wikipedia.org/wiki/Graph_homomorphism) from $(V,E)$ to itself.


Suppose $G=(V,E)$ is a simple, undirected graph. With $\text{Hom}(G,G)$ we denote the set of all graph homomorphisms $f:V\to V$.


[This post](https://mathoverflow.net/a/279252/8628) says that there is a largest $\text{Hom}(G,G)$-compatible set $E'\subseteq [V]^2$. Clearly $E'\supseteq E$.


**Question.** Do we have $E'=E$?



Largest edge set compatible with graph endomorphisms
No. In [this paper](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S1446788708000815) the define the *hull* of a graph $G$. The hull of $G$ has the same vertices of $G$ and has an edge between any pair of vertices that cannot be identified by any endomorphism of $G$. In other words, two vertices $x$ and $y$ of $G$ are adjacent in the hull of $G$ if and only if $f(x) \ne f(y)$ for all endomorphisms $f$ of $G$. In the same paper they show (and it is not difficult to see) that a graph is a core (has no homomorphism to a proper subgraph) if and only if its hull is a complete graph. Since it is known that almost all graphs are cores, this means that almost all graphs have complete hulls and thus $E' \ne E$.


If $E' = E$, then any pair of non-adjacent vertices can be identified by some endomorphism. This implies (but is not equivalent to) that the core of the graph (smallest subgraph the whole graph admits a homomorphism to) is a complete graph (which is equivalent to the clique and chromatic numbers of the graph being equal). Examples where $E' = E$ would include graphs that are transitive on non-edges and have a clique number equal to chromatic number. More specifically, the Paley graphs of square order have this property.


