A short proof of konigs matching theorem

A short proof of konigs matching theorem

1. A Short Proof of König's Matching Theorem Romeo Rizzi Journal of Graph Theory 報告者 : 陳政謙

2. Bipartite graphs

3. Vertex cover

4. Minimum vertex cover

5. Matching

6. Maximum matching

7. The relationship between minimum vertex cover and maximum matching For any graph G = (V, E), n (G) ≤ t (G), where n (G ) is the maximum cardinality of a matching of G and t (G ) is the minimum cardinality of a vertex cover of G.

8. König's theorem Let G be a bipartite graph. Then n (G) = t (G), where n (G) is the maximum cardinality of a matching of G and t (G) is the minimum cardinality of a vertex cover of G.

9. The proof of König's theorem Let G be a minimal counterexample. … … … n (G) < t (G) If there is a graph H smaller than G, then n (H) = t (H).

10. The proof of König's theorem Then G is connected, is not a circuit, nor a path. If G is not connected G G 1 G 2 … G n There exists at least one component G i which n ( G i ) < t ( G i ), where 1 ≤ i ≤ n. Then G is not a minimal counterexample.

11. The proof of König's theorem Then G is connected, is not a circuit, nor a path. If G is an odd path … If G is an even path … n (G) = t (G) =   n (G) = t (G) =  

12. The proof of König's theorem Then G is connected, is not a circuit, nor a path. Bipartite graphs cannot be odd cycle, so this case can be ignored. If G is an even cycle … n (G) = t (G) … … …

13. The proof of König's theorem So, G has a node of degree at least 3. Let u be such a node and v one of its neighbors. … … … u v We consider two cases: n (G - v) < n (G) and n (G - v) = n (G )

14. The proof of König's theorem Case 1: n (G - v) < n (G) B y minimality , G\v has a cover W’ with |W ’| = n (G - v) < n (G). … … … u v W’ ∪ {v} is a cover of G with cardinality n (G) at most . Hence, t (G ) ≤ n (G). The contradiction occurs.

15. The proof of König's theorem Case 2: n (G - v) = n (G ) T here exists a maximum matching M of G having no edge incident at v. … … … u v f Let W’ be a cover of G\f with |W’| = n (G - v) = n (G ). Hence, n (G) = t (G ). The contradiction occurs.

16. The proof of König's theorem By the proof, the contradiction occurs in both case 1 and case 2. So the assumption n (G) < t (G ) is not right. We conclude that n (G) = t (G ) holds in bipartite graphs.