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").



Neighborhood maps for graphs $G$ with $\delta(G) \geq 2$
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](http://gorogoro.cis.ibaraki.ac.jp/web/papers/PathFactorsKano.pdf), 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. 


