1. The problem: State and prove Konig's theorem, which relates the maximum matching size and minimum vertex cover size in bipartite graphs. 2. Statement of Konig's theorem: In any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. 3. Definitions: - A matching is a set of edges without common vertices. - A maximum matching is a matching with the largest possible number of edges. - A vertex cover is a set of vertices that touches every edge. - A minimum vertex cover is a vertex cover of smallest possible size. 4. Proof outline: - Let G = (U, V, E) be a bipartite graph with bipartition U and V. - Start with a maximum matching M. - Construct a set of vertices S reachable from unmatched vertices in U by alternating paths. 5. Construction detailed: - Define the set of unmatched vertices in U as U'. - Build the set S by including U' and then iteratively adding vertices reachable from S by edges not in M if from U, and edges in M if from V. 6. Define T as the set of vertices in V that are in S. 7. Then the set K = (U \ S) ∪ T forms a vertex cover. 8. Show that size(K) = size(M): - Count the edges matched in M and show that each corresponds to one unique vertex in K. 9. Conclude that the minimum vertex cover size equals the maximum matching size. This completes the proof of Konig's theorem.