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:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“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 (1911–1980)
“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. Rather—speaking loosely and without trying to answer either Pilate’s question or Tarski’s—a version is to be taken to be true when it offends no unyielding beliefs and none of its own precepts.”
—Nelson Goodman (b. 1906)