柯尼希定理

匹配与覆盖

图的顶点覆盖是指它的一个顶点集，该图的每一条边都至少有一个端点在这个顶点集中。如果该图没有一个点数更少的顶点覆盖，则称其为最小顶点覆盖。

图的匹配是指一个边的集合，每两条边都没有公共顶点。一个匹配称为最大匹配，如果不存在一个边数更多的匹配。

对于匹配的每一条边，顶点覆盖中至少有一个顶点为此边的端点，因此任何顶点覆盖集的元素个数都大于等于所有匹配集的元素个数。柯尼希定理表明对于二部图，这两个集合元素大小相同。

定理的陈述

在任意二部图中，最大匹配的边数等于最小顶点覆盖的顶点数。

证明

设 M 是一个最大匹配，因为顶点覆盖大于等于匹配集的大小，因此我们只需构造一个大小为 |M| 的顶点覆盖。构造如下：

将二部图的两部分分别记为 A 和 B。一个图关于匹配 M 的交错路（alternating path）是指一条从图中一个非匹配顶点出发，边在匹配集 M 与 （公式略） 中交错出现的道路。取顶点集 U 如下：对于 M 的每条边，如果存在一条交错路终止于该边在 B 中的端点，那么该端点属于 U，否则该边在 A 中的端点属于 U。因为 U 里每一个顶点都与 M 的一条边一一对应，所以 |U|=|M|。因此我们只需要证明 U 为一个顶点覆盖。

假设有一条边 ab 没有被 U 覆盖，即 a∈ A,b∈ B 都不在 U 中。如果 a 不是某一匹配的端点，那么 ab 本身就是一条从非匹配顶点出发的交错路，那么 b∈ U，矛盾。如果 a 属于某个匹配 ab'，那么 b'∈ U。这样， Pb'ab 就是一条交错路，从而 b∈ U，矛盾。

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Setting

A vertex cover in a graph is a set of vertices that includes at least one endpoint of every edge, and a vertex cover is minimum if no other vertex cover has fewer vertices. A matching in a graph is a set of edges no two of which share an endpoint, and a matching is maximum if no other matching has more edges.

Statement of the theorem

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Example

The bipartite graph shown in the above illustration has 14 vertices; a matching with six edges is shown in blue, and a vertex cover with six vertices is shown in red. There can be no smaller vertex cover, because any vertex cover has to include at least one endpoint of each matched edge (as well as of every other edge), so this is a minimum vertex cover.

Proofs

Constructive proof

The following proof provides a way of constructing a minimum vertex cover from a maximum matching. Let G=(V,E) be a bipartite graph and let A,B be the two parts of the vertex set V. Suppose that M is a maximum matching for G.

Construct the flow network G'_(∞) derived from G in such way that there are edges of capacity 1 from the source s to every vertex a∈ A and from every vertex b∈ B to the sink t, and of capacity +∞ from a b for any (a,b)∈ E.

Algorithm

The constructive proof described above provides an algorithm for producing a minimum vertex cover given a maximum matching. Thus, the Hopcroft–Karp algorithm for finding maximum matchings in bipartite graphs may also be used to solve the vertex cover problem efficiently in these graphs.

Despite the equivalence of the two problems from the point of view of exact solutions, they are not equivalent for approximation algorithms.

Non-bipartite graphs

For graphs that are not bipartite, the minimum vertex cover may be larger than the maximum matching. Moreover, the two problems are very different in complexity: maximum matchings can be found in polynomial time for any graph, while minimum vertex cover is NP-complete.

The complement of a vertex cover in any graph is an independent set, so a minimum vertex cover is complementary to a maximum independent set; finding maximum independent sets is another NP-complete problem.

History

Kőnig's theorem is named after the Hungarian mathematician Dénes Kőnig. Kőnig had announced in 1914 and published in 1916 the results that every regular bipartite graph has a perfect matching, and more generally that the chromatic index of any bipartite graph (that is, the minimum number of matchings into which it can be partitioned) equals its maximum degree – the latter statement is known as Kőnig's line coloring theorem.

Related theorems

Kőnig's theorem is equivalent to many other min-max theorems in graph theory and combinatorics, such as Hall's marriage theorem and Dilworth's theorem. Since bipartite matching is a special case of maximum flow, the theorem also results from the max-flow min-cut theorem.

Connections with perfect graphs

A graph is said to be perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique. Any bipartite graph is perfect, because each of its subgraphs is either bipartite or independent; in a bipartite graph that is not independent the chromatic number and the size of the largest clique are both two while in an independent set the chromatic number and clique number are both one.

Weighted variants

Konig's theorem can be extended to weighted graphs.

Egerváry's theorem for edge-weighted graphs

Jenő Egerváry (1931) considered graphs in which each edge e has a non-negative integer weight we. The weight vector is denoted by w. The w-weight of a matching is the sum of weights of the edges participating in the matching. A w-vertex-cover is a multiset of vertices ("multiset" means that each vertex may appear several times), in which each edge e is adjacent to at least we vertices.