Lagmental Vicfred

Kőnig's Theorem Equates Matching and Vertex Cover in Bipartite Graphs by Vicfred

tags: mathematics, paths, network flows, matchings

In a bipartite graph, maximum matching size equals minimum vertex-cover size. This is a compact note, but the quantifiers and hypotheses stay on the page.

Statement

Weighted paths minimize \(\sum_{e\in P}w(e)\), flows use values \(f:E\to\mathbf R_{\ge0}\) with conservation, and matchings enforce degree at most one. Each problem has a dual obstruction.

$$ G=(L\sqcup R,E)\ \text{bipartite} $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ \nu(G)=\tau(G) $$

Worked algebra

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \begin{array}{c}\text{maximum matching }M\\\Downarrow\ \text{alternating reachability from unmatched }L\\(L\setminus Z)\cup(R\cap Z)\text{ is a vertex cover of size }|M|\end{array} $$

Conceptual compression

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad G=(L\sqcup R,E)\ \text{bipartite},\\[5pt] \mathsf{C}\;&:\quad \nu(G)=\tau(G). \end{aligned} $$

Caveat

Dijkstra requires nonnegative edge weights, while flow capacities must be interpreted on a directed residual network even when the original graph is undirected.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \nu(G)=\tau(G) \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Thu 25 August 2011. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.