Kőnig's theorem (graph theory)
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.
Kőnig's theorem states that, in any bipartite graph, the minimum vertex cover set and the maximum matching set have in fact the same size.
Kőnig's theorem states that the equality between the sizes of the matching and the cover (in this example, both numbers are six) applies more generally to any bipartite graph.
The following proof provides a way of constructing a minimum vertex cover from a maximum matching.
__________ AG · x ≤ 1V.where x is a vector of size |E| in which each element represents the weight of an edge in the fractional matching.
0E is a vector of |E| zeros, so the second line indicates the constraint that the weights are non-negative.
1V is a vector of |V| ones and AG is the incidence matrix of G, so the third line indicates the constraint that the sum of weights near each vertex is at most 1.
__________ AGT · y ≥ 1E.where y is a vector of size |V| in which each element represents the weight of a vertex in the fractional cover.
This follows from the fact that in the fractional matching polytope of a bipartite graph, all extreme points have only integer coordinates, and the same is true for the fractional vertex-cover polytope.
Therefore the above theorem implies:[7] In any bipartite graph, the largest size of a matching equals the smallest size of a vertex cover.The constructive proof described above provides an algorithm for producing a minimum vertex cover given a maximum matching.
Bipartite maximum matchings can be approximated arbitrarily accurately in constant time by distributed algorithms; in contrast, approximating the minimum vertex cover of a bipartite graph requires at least logarithmic time.
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.
The equivalence between matching and covering articulated in Kőnig's theorem allows minimum vertex covers and maximum independent sets to be computed in polynomial time for bipartite graphs, despite the NP-completeness of these problems for more general graph families.
Kőnig had announced in 1914 and published in 1916 the results that every regular bipartite graph has a perfect matching,[11] 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[12] – the latter statement is known as Kőnig's line coloring theorem.
According to Biggs, Lloyd & Wilson (1976), Kőnig attributed the idea of studying matchings in bipartite graphs to his father, mathematician Gyula Kőnig.
In Hungarian, Kőnig's name has a double acute accent, but his theorem is sometimes spelled (incorrectly) in German characters, with an umlaut.
[14] 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,[15] 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.
For, each color class in a coloring of the complement of a bipartite graph is of size at most 2 and the classes of size 2 form a matching, a clique in the complement of a graph G is an independent set in G, and as we have already described an independent set in a bipartite graph G is a complement of a vertex cover in G. Thus, any matching M in a bipartite graph G with n vertices corresponds to a coloring of the complement of G with n-|M| colors, which by the perfection of complements of bipartite graphs corresponds to an independent set in G with n-|M| vertices, which corresponds to a vertex cover of G with M vertices.
Conversely, Kőnig's theorem proves the perfection of the complements of bipartite graphs, a result proven in a more explicit form by Gallai (1958).
A clique in the complement of the line graph of G is just a matching in G. And a coloring in the complement of the line graph of G, when G is bipartite, is a partition of the edges of G into subsets of edges sharing a common endpoint; the endpoints shared by each of these subsets form a vertex cover for G. Therefore, Kőnig's theorem itself can also be interpreted as stating that the complements of line graphs of bipartite graphs are perfect.
Jenő Egerváry (1931) considered graphs in which each edge e has a non-negative integer weight we.
Egerváry's theorem says:In any edge-weighted bipartite graph, the maximum w-weight of a matching equals the smallest number of vertices in a w-vertex-cover.The maximum w-weight of a fractional matching is given by the LP:[18] Maximize w · x Subject to: x ≥ 0E
__________ AG · x ≤ 1V.And the minimum number of vertices in a fractional w-vertex-cover is given by the dual LP:Minimize 1V · y Subject to: y ≥ 0V
__________ AGT · y ≥ w.As in the proof of Konig's theorem, the LP duality theorem implies that the optimal values are equal (for any graph), and the fact that the graph is bipartite implies that these programs have optimal solutions in which all values are integers.
One can consider a graph in which each vertex v has a non-negative integer weight bv.
Egerváry's theorem can be extended, using a similar argument, to graphs that have both edge-weights w and vertex-weights b:[18] In any edge-weighted vertex-weighted bipartite graph, the maximum w-weight of a b-matching equals the minimum b-weight of vertices in a w-vertex-cover.
