Proof of The Graph Theoretic Version
We first prove: If a bipartite graph G = (X + Y, E) = G(X, Y) has an X-saturating matching, then |NG(W)| ≥ |W| for all W ⊆ X.
Suppose M is a matching that saturates every vertex of X. Let the set of all vertices in Y matched by M to a given W be denoted as M(W). Therefore, |M(W)|=|W|, by the definition of matching. But M(W) ⊆ NG(W), since all elements of M(W) are neighbours of W. So, |NG(W)| ≥ |M(W)| and hence, |NG(W)| ≥ |W|.
Now we prove: If |NG(W)| ≥ |W| for all W ⊆ X, then G(X,Y) has a matching that saturates every vertex in X.
Assume for contradiction that G(X,Y) is a bipartite graph that has no matching that saturates all vertices of X. Let M be a maximum matching, and u a vertex not saturated by M. Consider all augmenting paths (i.e., paths in G alternately using edges outside and inside M) starting from u. Let the set of all points in Y connected to u by these augmenting paths be T, and the set of all points in X connected to u by these augmenting paths (including u itself) be W. No maximal augmenting path can end in a vertex in Y, lest we could augment M to a strictly larger matching. Thus every vertex in T is matched by M to a vertex in W. Conversely, every vertex v in W \ {u} is matched by M to a vertex in T (namely, the vertex preceding v on an augmenting path ending at v). Thus, M provides a bijection of W \ {u} and T, which implies |W| = |T| + 1. On the other hand, NG(W) ⊆ T: let v in Y be connected to a vertex w in W. If the edge (w,v) is in M, then v is in T by the previous part of the proof, otherwise we can take an augmenting path ending in w and extend it with v, showing that v is in T. Hence, |NG(W)| = |T| = |W| − 1, a contradiction.
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the words proof of the, proof of, proof, graph and/or version:
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (18721945)
“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (15641616)
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (18191891)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (18891919)
“Remember that you were a slave in the land of Egypt, and the LORD your God brought you out from there with a mighty hand and an outstretched arm; therefore the LORD your God commanded you to keep the sabbath day.”
—Bible: Hebrew, Deuteronomy 5:15.
See Exodus 22:8 for a different version of this fourth commandment.