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 Nielsen Jan 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.

  • $\begingroup$ (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. $\endgroup$ – 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.