# Version of Hall's marriage theorem in arbitrary finite graphs [closed]

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

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

## closed as off-topic by Chris Godsil, Boris Bukh, Ben Barber, Wojowu, Pace NielsenJan 11 at 21:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Chris Godsil, Boris Bukh, Wojowu, Pace Nielsen
If this question can be reworded to fit the rules in the help center, please edit the question.

• (What Gjergji said:) This is also Halls theorem in disguise, with V being of size at least 2. Just duplicate V, and have a directed graph from V to the copy with v goes to (copy of w) if v w is in the graph. Hall's theorem produces the bijection. Gerhard "Not A Single Rib Needed" Paseman, 2019.01.10. – Gerhard Paseman Jan 10 at 19:16

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.