König's theorem (graph theory)

From Wikipedia, the free encyclopedia

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.

[edit] 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,^[1] 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.^[2] 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.

[edit] 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.

[edit] 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.

[edit] 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₀). 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₀ 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₀ and E_m.

Then is a minimal vertex cover.

[edit] Proof

Partition of the vertices of a matched bipartite graph into even and odd levels, for the proof of König's theorem.

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_2j is defined for some j, let S_2j+1 be the set of vertices that are adjacent to vertices in S_2j via edges not in M, and that are not part of any previously-defined set. Each vertex in S_2j+1 must be an endpoint of an edge in M (else it would have been placed in S₀); for each such edge, since the other endpoint is not part of any previously-defined set, place that other endpoint in S_2j+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_2j, we may restart the process by placing a single vertex in S_2j+1 and then defining S_2j+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_2j+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_2j, 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_2j+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.

[edit] 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.

[edit] Notes

[edit] References

• Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976). Graph Theory 1736–1936. Oxford University Press, 203–207. ISBN 0-19-853916-9. 

• Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland, 74. ISBN 0-444-19451-7. 

• Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hungar. 9: 395–434. doi:10.1007/BF02020271. MR0124238. 

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

• Kőnig, Dénes (1931). "Gráfok és mátrixok". Matematikai és Fizikai Lapok 38: 116–119. 

• Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics 2: 253–267. doi:10.1016/0012-365X(72)90006-4. MR0302480.