Kőnig's theorem (graph theory)

For other uses, see König's theorem (disambiguation).

An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six.

In the mathematical area of graph theory, König's theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs.

A graph is bipartite if its vertices can be partitioned into two sets such that each edge has one endpoint in each set. A vertex cover in a graph is a set of vertices that includes at least one endpoint of each 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. König's theorem states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.

For graphs that are not bipartite, the maximum matching and minimum vertex cover 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's theorem is equivalent to numerous other min-max theorems in graph theory and combinatorics, such as Hall's marriage theorem and Dilworth's theorem.

König's theorem is named after the Hungarian mathematician Dénes König. König had announced in 1914 (Biggs et al 1976) 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. However, Bondy and Murty (1976) attribute König's theorem itself to a later paper of König (1931). According to Biggs et al, König attributed the idea of studying matchings in bipartite graphs to his father, mathematician Gyula König.

Example

The bipartite graph shown in the 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, so this is a minimum vertex cover. Similarly, there can be no larger matching, because any matched edge has to include at least one endpoint in the vertex cover, so this is a maximum matching. 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.

References

• Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976). Graph Theory 1736–1936. Oxford University Press. pp. 203–207. ISBN 0-19-853916-9.{{cite book}}: CS1 maint: multiple names: authors list (link)

• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. p. 74. ISBN 0-444-19451-7.{{cite book}}: CS1 maint: multiple names: authors list (link)

• König, Dénes (1916). "Graphok és alkalmazázuk a determinánsok és a halmazok elméletére". Mathematikai és Természettudományi Értesítő. 34: 104–119.

• König, Dénes (1931). "Graphs and matrices (Hungarian)". Mat. Fiz. Lapok. 38: 116–119.