Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge).


For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\subseteq V$ we let $N(S) = \bigcup \{N(v):v\in S\}$. A *bijective neighborhood map* is a bijection $\varphi:V\to V$ such that for all $v\in V$ we have $\varphi(v) \in N(v)$. 


Clearly, a necessary condition for a graph $G=(V,E)$ to have a bijective neighborhood map is that



> 
> (C) for all non-empty $S\subseteq V$ we have $|S|\leq |N(S)|$.
> 
> 
> 


(A very similar condition is central to [Hall's theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem).)


**Question.** Is (C) also sufficient for a graph $G$ to have a bijective neighborhood function?



Version of Hall's marriage theorem in arbitrary finite graphs
This is actually a special case of Hall's theorem itself, rather than an extension of it. To each such graph $G$ you can associate a bipartite graph $G'$ with vertex set two copies of $V$, which we can denote $V\_1,V\_2$, and edges between two vertices in different copies whenever their copies in $V$ were connected by an edge.


Now just notice that a bijective neighborhood function for $G$ is the same as a perfect matching for $G'$ and the condition is the same as the one in Hall's theorem, therefore it is necessary and sufficient.


