The concept of neighborhood maps was looked at in a previous question.
Let $G= (V,E)$ be a simple, undirected graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\} \in E\}$. Note that we always have $v\notin N(v)$. A function $f:V\to V$ is said to be a neighborhood map if $f(v)\in N(v)$ for all $v\in V$.
Does there exist a graph $G=(V,E)$ that admits an injective neighborhood map, but not a bijective one?
(Clearly, if such a graph exists, it is necessarily infinite.)
The answer is no. If $f:V \to V$ is an injective map, it is a disjoint union of finite cycles, copies of the successor function in $\mathbb{Z}$ and copies of the successor function in $\mathbb{N}$. Leave the first two kinds alone and replace all of the third kind by (the appropiate copy of) the function that swaps each even natural number with its successor. We now obtain a bijection and if the original function $f$ was a neighborhood map, the new one is also a neighborhood map. Note that the cardinality of $V$ is not relevant.
Not for finite graphs: a neighborhood map takes $V$ to itself, so injective implies bijective.
