Hall's Marriage Theorem - Proof of The Graph Theoretic Version

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 WX.

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 (1821–1867)

    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)

    The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.
    Charles Baudelaire (1821–1867)

    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 (1889–1919)

    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.