【正文】 ) Find a perfect matching in G2 by induction. Find a perfect matching in G1 by induction. G1 G2 Then we are done. Proof of Hall’s Theorem S N(S) Why there is a perfect matching in G2? To apply Hall’s, we want to show for any subset T of S, |N(T) G2| = |T|. T |N(T) G2| G2 Hall’s Theorem: If |N(S)| = |S| for every subset S of V, then there is a perfect matching. Proof of Hall’s Theorem S N(S) Why there is a perfect matching in G2? For any subset T S, N(T) is contained in G2. Hence, |N(T) G2| = |N(T)| = |T|. Therefore, by induction, there is a perfect matching in G2. T G2 Find a perfect matching in G2 by induction. |N(T) G2| Why there is a perfect matching in G1? Proof of Hall’s Theorem S N(S) T N(T) G1 For any subset T, we want to show |N(T) G1| = |T| to apply induction. 1. Consider T, by assumption, |N(T)| = |T| 2. Can we conclude that |N(T) G1| = |T|? 3. No, because N(T) may intersect N(S)! Now what? Why there is a perfect matching in G1? Proof of Hall’s Theorem S N(S) T N(T) G1 (red) |S|=|N(S)| For any subset T, we want to show |N(T) G1| = |T| to apply induction. 1. Consider S T, by assumption, |N(S T)| = |S T| (the green areas). 2. Since |S|=|N(S)|, |N(S T) – N(S)| = |S T S| (the red areas). 3. So |N(T) G1| = |N(S T) – N(S)| = |S T – S| = |T|, as required. N(S T) (green) Hall’s Theorem: If |N(S)| = |S| for every subset S of V, then there is a perfect matching. Proof of Hall’s Theorem Case 2: Suppose there is a subset S with |N(S)| = |S|. S N(S) Divide the graph into two smaller graphs G1 and G2 (so we can apply induction) Find a perfect matching in G2 by induction. Find a perfect matching in G1 by induction. G1 G2 Now we are done. Bipartite Matching and Hall’s Theorem Hall’s theorem is a fundamental theorem in graph theory. In this course, it is important to learn 1. how to use bipartite matching to solve problems, and 2. how to apply Hall’s theorem. The proof of Hall’s theorem is optional. 。Bipartite Matching Lecture 8: Oct 7 This Lecture Graph matching is an important problem in graph theory. It has many applications and is the basis of more advanced problems. In the last lecture we consider the stable matching problem. Today we will study the bipartite matching problem.