König's theorem (graph theory)

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.

Setting

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. Since bipartite matching is a special case of maximal flow, the theorem also results from the max flow min cut theorem.

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, [In a poster displayed at the 1998 ICM in Berlin and again at the Bled'07 International Conference on Graph Theory, Harald Gropp has pointed out that the same result already appears in the language of configurations in the 1894 thesis of Ernst Steinitz.] 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. [Biggs et al. (1976).] 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. Note that, although Kőnig's name is properly spelled with a double acute accent, the theorem named after him is customarily spelled with an umlaut.

Theorem's statement

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, 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.

Algorithm

Consider a bipartite graph where the vertices are partitioned into left ($L$) and right ($R$) sets. Suppose there is a maximal matching which partitions the edges into those used in the matching ($E\_m$) and those not ($E\_0$). Let $T$ consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from $E\_0$ and right-to-left along edges from $E\_m$. This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from $E\_0$ and $E\_m$.

Then $(L\; setminus\; T)\; cup\; (R\; cap\; T)$ is a minimal vertex cover.

Proof

Suppose that "G" is a bipartite graph, with a given matching "M". In order to prove König's theorem, we must show that either "M" is non-maximal or there exists a vertex cover equal in size to "M".

To do so, first check whether all vertices are already matched by "M". In this case, one part of the bipartition forms a vertex cover of size |"M"| and we are done. Otherwise, partition the vertices of "G" into subsets "S"_"i" as follows. Let "S"₀ consist of all vertices that are left unmatched by "M". Once "S"_2"j" is defined for some "j", let "S"_2"j"+1 be the set of vertices that are adjacent to vertices in "S"_2"j" via edges not in "M", and that are not part of any previously-defined set. Each vertex in "S"_2"j"+1 must be an endpoint of an edge in "M" (else it would have been placed in "S"₀); for each such edge, if the other endpoint is not part of this or any previously-defined set, place that other endpoint in "S"_2"j"+2. The illustration shows this partition for a graph and matching isomorphic to the one in the example. If, at any stage of this process, there are no vertices adjacent to "S"_2"j", we may restart the process by placing a single vertex in "S"_2"j"+1 and then defining "S"_2"j"+2 as before.

For each vertex "v" in "G", in a set "S"_"i" one can find a path from "v" to a vertex in "S"_"i"-1, and so on up one level at a time ending either at an unmatched vertex or at a level containing a single vertex; this is an "alternating path" meaning that the edges in the path are alternately in and out of the matching.If there exists any matched edge "uv" between two vertices "u" and "v" in the same odd-level subset "S"_2"j"+1, the two alternating paths for "u" and "v" can be connected via "u" and "v" to a single alternating path; this path cannot have any repeated vertices, by bipartiteness, so it must start and end at an unmatched vertex. Removing from "M" the matched edges in this path and replacing them by the unmatched path edges produces a larger matching, so in this case "M" cannot be maximal. Similarly, if there exists an unmatched edge "uv" between two vertices "u" and "v" in the same even-level subset "S"_2"j", we can form an alternating path between two unmatched vertices and increase the size of the matching, proving that "M" is not maximal. There cannot be any matched edges between vertices in even level subset, for every matched vertex in an even level subset is connected by its single matched edge to a vertex in the previous level.

Thus, if "M" is maximum, each matched edge has a single endpoint in one of the odd-level subsets "S"_2"j"+1, and each unmatched edge has at least one of its endpoints in one of the odd-level subsets. Therefore, the union of the odd-level subsets forms a vertex cover, with size equal to the size of "M". It must be a minimum vertex cover, for no smaller set of vertices could cover every edge in "M". Therefore, the maximum matching and minimum vertex cover have the same size.

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.

A graph is perfect if and only if its complement is perfect (Lovász 1972), and König's theorem can be seen as equivalent to the statement that the complement of a bipartite graph is perfect. 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).

One can also connect König's theorem to a different class of perfect graphs, the line graphs of bipartite graphs. If "G" is a graph, the line graph "L"("G") has a vertex for each edge of "G", and an edge for each pair of adjacent edges in "G". Thus, the chromatic number of "L"("G") equals the chromatic index of "G". If "G" is bipartite, the cliques in "L"("G") are exactly the sets of edges in "G" sharing a common endpoint. Therefore, the result of König (1916) that the chromatic index equals the degree in any bipartite graph can be interpreted as stating that any line graph of a bipartite graph is perfect.

Since line graphs of bipartite graphs are perfect, the complements of line graphs of bipartite graphs are also perfect. 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.

Notes

References

*cite book
author = Biggs, N. L.; Lloyd, E. K.; Wilson, R. J.
title = Graph Theory 1736–1936
publisher = Oxford University Press
year = 1976
id = ISBN 0-19-853916-9
pages = 203–207

*cite book
author = Bondy, J. A.; Murty, U. S. R.
title = Graph Theory with Applications
publisher = North Holland
year = 1976
id = ISBN 0-444-19451-7
pages = 74

* cite journal
author = Gallai, Tibor
authorlink = Tibor Gallai
title = Maximum-minimum Sätze über Graphen
year = 1958
journal = Acta Math. Acad. Sci. Hungar.
volume = 9
pages = 395–434
id = MathSciNet | id = 0124238
doi = 10.1007/BF02020271

*cite journal
author = Kőnig, Dénes
authorlink = Dénes Kőnig
title = Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére
journal = Matematikai és Természettudományi Értesítő
volume = 34
year = 1916
pages = 104–119

*cite journal
author = Kőnig, Dénes
authorlink = Dénes Kőnig
title = Gráfok és mátrixok
journal = Matematikai és Fizikai Lapok
volume = 38
year = 1931
pages = 116–119

* cite journal
author = Lovász, László
authorlink = László Lovász
year = 1972
title = Normal hypergraphs and the perfect graph conjecture
journal = Discrete Mathematics
volume = 2
pages = 253–267
id = MathSciNet | id = 0302480
doi = 10.1016/0012-365X(72)90006-4