-1
$\begingroup$

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?

$\endgroup$

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
7
$\begingroup$

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.

$\endgroup$

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