Is there an infinite connected simple undirected graph $G=(V, E)$ such that the identity map $\text{id}\_V: V\to V$ is the only graph self-homomorphism from $G$ to itself?


(A graph self-homomorphism is a map $f: V\to V$ such that for all $e\in E$ with $e = \{v, w\}$ we have $\{f(v), f(w)\} \in E$.)



Infinite strongly rigid graphs
Unfortunately, I don't have enough reputation to comment, but there seems to be a problem with both solutions suggested so far: The graphs are bipartite, meaning that they allow a homomorphism to a single edge, which of course is a non-trivial homomorphism from the graph to itself (note that homomorphisms are not assumed to be injective).


However, here is a more complicated construction which hopefully takes care of this:


Let $H\_0 = K\_3$. For $i \geq 1$ let $H\_i$ be a triangle free graph such that $\chi(H\_i) > \chi(H\_{i-1})$ and such that the only homomorphisms from $H\_i$ to itself are automorphisms (there is for example a family of Kneser graphs with this property). 


Enumerate the vertices of the disjoint union $\bigcup \_{i \geq 0} H\_i$ as $(v\_j)\_{j \geq 1}$ such that $v\_j \in H\_i$ for some $i < j$.


Now define a sequence $G\_n$ as follows:


* $G\_0 = H\_0$.
* For $i > 0$ let $l$ be the maximum of the diameters of $G\_{i-1}$ and $H\_i$ and connect one vertex of $H\_i$ to $v\_i$ by a path of length $l$.
* Let $G$ be the direct limit of this construction.


There is no homomorphism from $K\_3$ to a triangle free graph, hence $G\_0$ must be fixed by every homomorphism.


There is no homomorphism from $G$ to $H$ if $\chi (H) < \chi (G)$, hence $H\_i$ cannot be mapped into $G\_{i-1}$ (plus the paths leading to $H\_j$ for $j>i$). Since Homomorphisms never increase distances, i.e. if $f$ is a homomorphism, then $d(x,y) \geq d(f(x),f(y))$, this together with the fact that $d(H\_i,H\_0)$ is bounded by the diameter of $G\_i$ implies that the image of $H\_i$ must intersect $H\_i$. Consequently $H\_i$ must map to itself---if the image of $H\_i$ intersected one of the paths attached to $H\_i$, then this would give a homomorphism $H\_i \to H\_i$ which is not an automorphism.


So far we showed that each $H\_i$ is fixed setwise by every self-homomorphism of $G$. Finally, the structure between the $H\_i$ guarantees that every $H\_i$ must be fixed pointwise: if $v\_j \in H\_i$, then it is the unique vertex in $H\_i$ which minimises the distance to $H\_j$.


