Neighborhood maps for graphs $G$ with $\delta(G) \geq 2$ 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$.
If $G$ is a graph such that very vertex has degree $\geq 2$, does there exist an injective neighborhood map for $G$?
Real world inspiration. At a work seminar I attended recently, each participant knew a couple of other people. Everyone was given a task and could select one of their acquaintances for help on their task. We were asked to select our helping partner in such a manner that no-one had to help more than 1 other person with their task (whence "injective neighborhood map").
 A: Note that $K_2$ and any cycle admit injective neighborhood maps.
More generally, a $(1,2)$-factor of a graph $G$ is a spanning subgraph $F$ where each vertex has degree $1$ or $2$. Such an $F$ is a disjoint union of cycles and paths. I will call a $(1,2)$-factor "short" if every vertex of degree $2$ (in $F$) belongs to a cycle; in other words, the only paths in $F$ are isolated edges.  
Given a neighborhood map $f:V(G)\to V(G)$, consider the set $F$ of edges $(v,f(v))$ for $v \in V$. I claim that $F$ is a short $(1,2)$-factor of $G$.
Indeed, pick any $v_0 \in V$ and consider $v_1=f(v_0)$. There are two cases: 


*

*$f(v_1)=v_0$, in which case $(v_0,v_1)\in F$ is an isolated edge of $F$ and $\deg_F(v_0)=\deg_F(v_1)=1$, or

*$f(v_1) \neq v_0$. Call $v_2=f(v_1)$ and keep going, with $v_{n+1}=f(v_n)$ for $n=1,2,3,\ldots$. This is a walk in $G$ which has to end at $v_0$ (it can't "stop" since every vertex is mapped somewhere by $f$, and it can't hit any vertex $v_i, i\ge 1$ due to injectivity). So eventually you will have formed a $2$-cycle $v_0,v_1,\ldots,v_m$ for some $m$, with the edges $(v_i,v_{i+1 \bmod m})\in F$ and $\deg_F(v_i)=2$. 


Conversely, if a graph $G$ admits a short $(1,2)$-factor, then it admits an injective neighborhood map: flip the vertices of the $1$-factor and orient the edges of each cycle in the $2$-factor arbitrarily, mapping each vertex to where the oriented edge points to. 
===
Therefore, graphs with an injective neighborhood map are the same as graphs with short $(1,2)$-factors. In particular, graphs with a perfect matching, or with a $2$-factor, have an injective neighborhood map. On the other hand, not all graphs with min deg 2 have a short $(1,2)$-factor: for example, $K_{2,3}$ does not. (By the way, there's no need to require min deg 2 – lots of graphs with min deg 1 have an injective neighborhood map).
There is some literature on $(1,2)$-factors, for example here, but I'm not familiar with the "short $(1,2)$-factor" condition. There may well be a different way to look at this that I'm not aware of. 
