Page 681 - Discrete Mathematics and Its Applications

660 10 / Graphs

Proof: We first prove the only if part of the theorem. To do so, suppose that there is a complete
matching M from V 1 to V 2 . Then, if A ⊆ V 1 , for every vertex v ∈ A, there is an edge in M
connecting v to a vertex in V 2 . Consequently, there are at least as many vertices in V 2 that are
neighbors of vertices in V 1 as there are vertices in V 1 . It follows that |N(A)|≥|A|.
To prove the if part of the theorem, the more difficult part, we need to show that if
|N(A)|≥|A| for all A ⊆ V 1 , then there is a complete matching M from V 1 to V 2 . We will
use strong induction on |V 1 | to prove this.
Basis step: If |V 1 |= 1, then V 1 contains a single vertex v 0 . Because |N({v 0 })|≥|{v 0 }| = 1,
there is at least one edge connecting v 0 and a vertex w 0 ∈ V 2 . Any such edge forms a complete
matching from V 1 to V 2 .
Inductive step: We first state the inductive hypothesis.

Inductive hypothesis: Let k be a positive integer. If G = (V, E) is a bipartite graph with bipar-
tition (V 1 ,V 2 ), and |V 1 |= j ≤ k, then there is a complete matching M from V 1 to V 2 whenever
the condition that |N(A)|≥|A| for all A ⊆ V 1 is met.
Now suppose that H = (W, F) is a bipartite graph with bipartition (W 1 ,W 2 ) and |W 1 |=
k + 1. We will prove that the inductive holds using a proof by cases, using two case. Case (i)
applies when for all integers j with 1 ≤ j ≤ k, the vertices in every set of j elements from W 1 are
adjacent to at least j + 1 elements of W 2 . Case (ii) applies when for some j with 1 ≤ j ≤ k there

isasubsetW ofj verticessuchthatthereareexactly j neighborsoftheseverticesinW 2 .Because
1
eitherCase (i)orCase (ii)holds,weneedonlyconsiderthesecasestocompletetheinductivestep.
Case (i): Suppose that for all integers j with 1 ≤ j ≤ k, the vertices in every subset of j elements
from W 1 are adjacent to at least j + 1 elements of W 2 . Then, we select a vertex v ∈ W 1 and an
element w ∈ N({v}), which must exist by our assumption that |N({v}|≥|{v}| = 1. We delete

v and w and all edges incident to them from H. This produces a bipartite graph H with
bipartition (W 1 −{v},W 2 −{w}). Because |W 1 −{v}| = k, the inductive hypothesis tells us
there is a complete matching from W 1 −{v} to W 2 −{w}. Adding the edge from v to w to this
complete matching produces a complete matching from W 1 to W 2 .

Case (ii): Suppose that for some j with 1 ≤ j ≤ k, there is a subset W of j vertices such that
1

there are exactly j neighbors of these vertices in W 2 . Let W be the set of these neighbors. Then,
2

by the inductive hypothesis there is a complete matching from W to W . Remove these 2j
1 2
vertices from W 1 and W 2 and all incident edges to produce a bipartite graph K with bipartition

(W 1 − W ,W 2 − W ).

2
1
We will show that the graph K satisfies the condition |N(A)|≥|A| for all subsets A of

W 1 − W . If not, there would be a subset of t vertices of W 1 − W where 1 ≤ t ≤ k + 1 − j
1
1
such that the vertices in this subset have fewer than t vertices of W 2 − W as neighbors. Then,

2
the set of j + t vertices of W 1 consisting of these t vertices together with the j vertices we
removed from W 1 has fewer than j + t neighbors in W 2 , contradicting the hypothesis that
|N(A)|≥|A| for all A ⊆ W 1 .
PHILIP HALL (1904–1982) Philip Hall grew up in London, where his mother was a dressmaker. He won a
scholarship for board school reserved for needy children, and later a scholarship to King’s College of Cambridge
University. He received his bachelors degree in 1925. In 1926, unsure of his career goals, he took a civil service
exam, but decided to continue his studies at Cambridge after failing.
In 1927 Hall was elected to a fellowship at King’s College; soon after, he made his first important discovery
in group theory. The results he proved are now known as Hall’s theorems. In 1933 he was appointed as a Lecturer
at Cambridge, where he remained until 1941. During World War II he worked as a cryptographer at Bletchley
Park breaking Italian and Japanese codes. At the end of the war, Hall returned to King’s College, and was soon
promoted. In 1953 he was appointed to the Sadleirian Chair. His work during the 1950s proved to be extremely
influential to the rapid development of group theory during the 1960s.
Hall loved poetry and recited it beautifully in Italian and Japanese, as well as English. He was interested in art, music, and
botany. He was quite shy and disliked large groups of people. Hall had an incredibly broad and varied knowledge, and was respected
for his integrity, intellectual standards, and judgement. He was beloved by his students.