Neighbour set
For any set S of vertices in G, we define the neighbour set of S in G to be the set of all vertices adjacent to the vertices in S, and this set is denoted by N(S)
Hall's Condition for neighbour set
Let G be a bipartite graph with bipartition (X,Y). Then G contains a matching that saturates every vertex in X if and only if\[\left | N(S) \right |\geqslant \left | S \right |\] for all \[S\subseteq X\]
Proof
Suppose that G contains a matching M which saturates every vertex in X and let S subset of X
Clearly \[\left | N(S) \right |\geqslant \left | S \right |\]
Conversely suppose that \[\left | N(S) \right |\geqslant \left | S \right |\]
Assume contrary that G contains no matching saturates every vertex in X.
Let M* be a maximum matching in G.
By our assumption M* does not saturate all vertex in X.
Let u be a M*-unsaturated vertex in X, and let Z denote the set of all vertices connected to u by M*-alternaing paths.
Since M* is a maximum matching, it follows from the theorem"A matching M in G is a maximum matching if and only if G contains no augmenting path"
u is the only M* unsaturated vertex in Z.
Set \[S=Z\cap X\text{ and }T=Z\cap Y\]
Clearly, the vertices in S-{u} are matched under M* with the vertices in T.
therefore\[\left | T \right |=\left | S \right |-1\]
and \[N(S)\supseteq T\]
In fact, we have N(S)=T, since every vertex in N(S) is connected to u by an M* alternating path.
Suppose that y element of Y-T has a neighbour v element of S. The edge vy cannot be in M*. Since u is unsaturated and the rest of S is matched to T by M*. Thus adding vy to an M* alternating path reaching v yields an M*- alternating path to y. This contradicts y not an element of T, and hence vy cannot exist.
combaining both results\[\left | N(S) \right |=\left | T \right |=\left | S \right |-1<\left | S \right |\]
Contradicting our assumption.
Hence G contains a matching that saturates every vertex in G
0 Comments