Notion of neighborhood in Hall's Theorem

Question

In Hall's Theorem, should we refer to $N(S)$ as $\bigcup_{x \in S}N(x)$ or as $\bigcup_{x \in S}N(x) - S$? I guess that the second definition is the one used in the theorem.

Answer 1

I will answer "what should $N(S)$ mean in Hall's theorem?" because that's clearly what the question wants to be asking, but I find the notation in the question ambiguous.

There are two options for the statement of Hall's theorem. The first is much more common, but I will include both, because it's more interesting to compare definitions that way.

1. In a bipartite graph $G$ with bipartition $(X,Y)$, we can say that Hall's condition (for checking if $G$ has an $X$-saturating matching) is that $|N(S)| \ge |S|$ for all $S \subseteq X$. Here, $N(S)$ is defined as the set of all vertices of $G$ which are adjacent to some vertex in $S$; $N(S)$ is necessarily a subset of $Y$. The only clarification we need to make is that vertices of $S$ are not automatically included in $N(S)$.
2. In a bipartite graph $G$ wtith bipartition $(X,Y)$, we can say that Hall's condition (for checking if $G$ has a perfect matching) is that $|N(S)| \ge |S|$ for all $S \subseteq X \cup Y$. (This is much less common; see exercise 3.1.22 in West's Introduction to Graph Theory.) Here, $N(S)$ can still be defined as the set of all vertices of $G$ which are adjacent to some vertex in $S$. Vertices of $S$ are neither automatically included nor automatically excluded from $N(S)$.

In both cases, we can define $N(S)$ to contain every vertex $v \in V(G)$ such that $v$ has a neighbor in $S$, without care for whether $v \in S$ and $v \notin S$. This is also the most common definition of $N(S)$.

Other definitions encountered in graph theory include:

• The set of vertices which have a neighbor in $S$, but are not themselves in $S$; this is common in the study of vertex expansion, where it is also commonly denoted $N(S)$. As an alternative, Wikipedia uses the notation $\partial_{\text{out}}(S)$ in the article on expander graphs. The first and by far more common version of Hall's theorem still holds if we check the condition $|\partial_{\text{out}}(S)| \ge |S|$, because in the first version of Hall's theorem, vertices in $S$ cannot possibly be adjacent. For the second version of Hall's theorem, this condition is too strict.
• The set of vertices with have a neighbor in $S$, or are themselves in $S$. This is more commonly called the closed neighborhood of $S$. Notation varies, but $\overline N(S)$ is a common version that distinguishes it from $N(S)$. Neither version of Hall's theorem will work with this definition.