To prove König's theorem, start with a max matching . Build a vertex cover by taking all matched vertices in one group plus unmatched vertices in the other that cannot be reached from unmatched vertices via alternating paths. This construction gives a cover of size .
Since any vertex cover must include at least one endpoint of each matched edge, and these edges are disjoint, the minimum cover has size at least . Therefore, both equal .