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:
“The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
—Charles Baudelaire (18211867)
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutationa proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (17091784)
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (19111980)
“Truth cannot be defined or tested by agreement with the world; for not only do truths differ for different worlds but the nature of agreement between a world apart from it is notoriously nebulous. Ratherspeaking loosely and without trying to answer either Pilates question or Tarskisa version is to be taken to be true when it offends no unyielding beliefs and none of its own precepts.”
—Nelson Goodman (b. 1906)