📐 König-Egerváry Theorem

In a bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover.

Proof: A vertex cover must include at least one endpoint of each matched edge, so cover size $\\geq$ matching size. For equality: let $M$ be maximum and $U \\subseteq X$ be vertices reachable from unmatched $X$-vertices via $M$-alternating paths. Set $C = (X \\setminus U) \\cup (Y \\cap U)$. Then $|C| =...

From: Introduction to Graph Theory

Learn more: https://west-graphs-deploy.vercel.app/#/section/8

Explore all courses: https://mathacademy-cyan.vercel.app