Kőnig's theorem (graph theory)
Kőnig's theorem, also called the Kőnig–Watanabe theorem in matching theory, states that the maximum cardinality of a matching in a finite bipartite graph equals the minimum cardinality of a vertex cover in the same graph. In standard notation, if (G=(X\cup Y,E)) is bipartite, then
[ \nu(G)=\tau(G), ]
where (\nu(G)) denotes the largest number of pairwise vertex-disjoint edges and (\tau(G)) denotes the smallest number of vertices incident with every edge.
The theorem is a central min–max theorem of finite graph theory. Its restriction to bipartite graphs is essential: every graph satisfies (\nu(G)\leq \tau(G)), but equality does not generally hold outside the bipartite case. For example, a triangle has maximum matching size (1), while every vertex cover contains at least (2) vertices.
Historical development
The theorem emerged from the early development of systematic matching theory. Dénes Kőnig and You Watanabe established the bipartite matching–cover identity in 1931 through analyses of alternating paths and edge arrangements in bipartite graphs. Their formulations expressed the same min–max relation, although the terminology of matchings and vertex covers had not yet reached its modern standardized form.
Kőnig's broader work placed the result within the structural study of graphs, while Watanabe's treatment emphasized the transformation of a nonmaximum matching by an alternating chain. This transformation later became known as augmenting-path augmentation. The resulting proof method supplies both the equality and an explicit correspondence between a maximum matching and a minimum vertex cover.
The theorem became known principally under Kőnig's name in general graph-theoretic literature. The compound name Kőnig–Watanabe theorem remains in use in treatments that distinguish the original matching–cover result from its weighted and matrix-theoretic extensions.
Definitions
A matching (M\subseteq E) is a set of edges such that no two edges in (M) share an endpoint. A vertex is saturated by (M) when it is incident with an edge of (M). A maximum matching is a matching of greatest possible cardinality, denoted by (\nu(G)).
A vertex cover is a subset (C\subseteq X\cup Y) such that every edge has at least one endpoint in (C). A minimum vertex cover has the least possible cardinality, denoted by (\tau(G)).
For any graph, the inequality
[ \nu(G)\leq \tau(G) ]
follows because the edges of a matching have disjoint endpoints. A vertex cover must therefore contain a distinct endpoint for each matched edge. Kőnig's theorem asserts that bipartiteness makes this elementary lower bound attainable.
Alternating-path proof
Consider a bipartite graph (G=(X\cup Y,E)) with a maximum matching (M). Denote by (U\subseteq X) the vertices in (X) that are not saturated by (M). An (M)-alternating path from (U) traverses edges outside (M) from (X) to (Y), and traverses edges in (M) from (Y) back to (X).
Let (Z) be the set of all vertices reachable from (U) by such alternating paths. Its intersections with the two parts are written as
[ Z_X=Z\cap X \qquad\text{and}\qquad Z_Y=Z\cap Y. ]
The set
[ C=(X\setminus Z_X)\cup Z_Y ]
is a vertex cover. If an edge (xy), with (x\in X) and (y\in Y), had neither endpoint in (C), then (x) would belong to (Z_X) while (y) would not belong to (Z_Y). An unmatched edge from such an (x) would extend an alternating path to (y). If (xy) were matched, the alternating path reaching (x) would already pass through its matched neighbor (y). Either case contradicts (y\notin Z_Y).
Every vertex in (Z_Y) is saturated by (M). Otherwise, an alternating path from an unsaturated vertex of (X) to an unsaturated vertex of (Y) would be an augmenting path, contradicting the maximal cardinality of (M). Furthermore, the matching pairs the vertices of (Z_Y) bijectively with the vertices of (Z_X\setminus U). Consequently,
[ |Z_Y|=|Z_X|-|U|. ]
Since (M) saturates exactly the vertices of (X\setminus U),
[ |M|=|X|-|U|. ]
The size of the constructed cover is therefore
[ \begin{aligned} |C| &=|X\setminus Z_X|+|Z_Y|\ &=|X|-|Z_X|+|Z_X|-|U|\ &=|X|-|U|\ &=|M|. \end{aligned} ]
The general inequality (\nu(G)\leq\tau(G)), combined with the existence of this cover, yields (\nu(G)=\tau(G)).
Relation to augmenting paths
The proof is closely connected with Berge's lemma, which states that a matching is maximum exactly when no augmenting path exists. The reachable-set construction records the obstruction that remains after all augmenting paths have disappeared.
This relationship gives the theorem an algorithmic interpretation. A maximum matching obtained through repeated augmentation determines a minimum vertex cover through alternating reachability. The matching and cover thus serve as mutually verifying optimal solutions: the cover bounds the size of every matching from above, while the matching attains that bound.
For a graph (G=(X\cup Y,E)), the classical augmenting-path method leads to polynomial-time matching algorithms. More refined implementations include the Hopcroft–Karp algorithm, which computes a maximum matching in time
[ O!\left(|E|\sqrt{|X|+|Y|}\right). ]
The corresponding minimum vertex cover follows from the final alternating-reachability structure without changing the asymptotic bound.
Linear-programming interpretation
Kőnig's theorem is also an integrality statement for a pair of dual linear programs. The fractional matching problem assigns a nonnegative variable (x_e) to each edge and maximizes
[ \sum_{e\in E}x_e ]
subject to
[ \sum_{e\ni v}x_e\leq 1 ]
for every vertex (v). Its dual assigns a nonnegative variable (y_v) to each vertex and minimizes
[ \sum_{v\in V}y_v ]
subject to
[ y_u+y_v\geq 1 ]
for every edge (uv).
In an arbitrary graph, these programs describe fractional matchings and fractional vertex covers. For bipartite graphs, the relevant constraint matrices are totally unimodular, so integral optimal solutions exist whenever the data are integral. The integral primal solutions are matchings, while integral dual solutions can be identified with vertex covers. Strong duality then gives the equality of their optimum cardinalities.
This formulation places the theorem within the wider theory of combinatorial optimization. It also explains why closely related statements occur in assignment problems, network flows, and integer programming. Jenő Egerváry developed the corresponding weighted duality in 1931, producing the result commonly called the Kőnig–Egerváry theorem in its matrix and weighted-assignment forms.
Equivalence with other bipartite results
Kőnig's theorem is equivalent, through standard finite reductions, to several foundational results about bipartite incidence structures. Hall's marriage theorem characterizes when a bipartite graph contains a matching saturating one part. Applied to suitable subgraphs, Hall's condition yields the matching–cover equality; conversely, Kőnig's theorem applied to a graph lacking a saturating matching produces a set violating Hall's condition.
A matrix formulation arises from the incidence matrix of a bipartite graph. Under this correspondence, a matching becomes a collection of nonzero entries with no two in the same row or column. A vertex cover becomes a collection of rows and columns containing every nonzero entry. The theorem therefore states that the largest number of mutually independent nonzero entries equals the smallest number of rows and columns covering all nonzero entries.
The theorem also follows from the integral form of the max-flow min-cut theorem. A bipartite graph can be represented by a directed network in which the source is joined to one bipartition class, graph edges run between the two classes, and the second class is joined to the sink. Unit capacities convert integral flows into matchings, while minimum cuts correspond to vertex covers of the same size.
Limitations and extensions
The equality does not extend unchanged to nonbipartite graphs because odd cycles create an integrality obstruction. In a cycle of length (2k+1), a maximum matching has size (k), whereas a minimum vertex cover has size (k+1). The fractional linear programs still have equal optimum values by linear-programming duality, but their integral optimum solutions need not coincide.
For general graphs, maximum matching remains polynomial-time computable through methods based on blossoms. The associated polyhedral description requires additional odd-set inequalities that have no counterpart in the elementary bipartite formulation. Thus, Kőnig's theorem identifies a structural property particular to bipartite graphs rather than a universal equality between matching and covering parameters.