In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 area of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, König's theorem, proved by Dénes Kőnig

Dénes König

Dénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....

 in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

s. It was discovered independently, also in 1931, by Jenő Egerváry

Jenő Egerváry

Jenő Egerváry was a Hungarian mathematician.-Biography:Egerváry was born in Debrecen in 1891. In 1914, he received his doctorate at the Pázmány Péter University in Budapest, where he studied under the supervision of Lipót Fejér...

 in the more general case of weighted 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

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

. The complement of a vertex cover in any graph is an independent set

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

, 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

Marriage theorem

In mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets...

 and Dilworth's theorem

Dilworth's theorem

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...

. Since bipartite matching is a special case of maximum 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

Dénes König

Dénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....

. Kőnig had announced in 1914 and published in 1916 the results that every regular

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 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

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

 – the latter statement is known as König's Line Coloring Theorem. 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

Double acute accent

The double acute accent is a diacritic mark of the Latin script. It is used primarily in written Hungarian, and consequently is sometimes referred to as Hungarumlaut, a portmanteau of Hungarian umlaut...

, the theorem named after him is customarily spelled with an umlaut.

Statement of the theorem

In any bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

, 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 () and right () sets. Suppose there is a maximum matching which partitions the edges into those used in the matching () and those not (). Let consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from and right-to-left along edges from . 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 and .

Then is a minimum vertex cover. Intuitively, vertices in are added if they are in and subtracted if they are in to obtain the minimum vertex cover. 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.

Proof

Suppose that G=(V,E) is a bipartite graph, where V = A ∪ B. Let M be a matching for G.

We must show either G has a vertex cover C of size |M|, or M is not a maximum matching.

First, if M is a perfect matching, then M is maximum. In this case, every edge is incident to exactly one vertex on either side,
so any partition of G is a vertex cover of size |M| and we are done.

Otherwise, use an alternating path argument. An alternating path is a path where the edges alternate between M and E \ M.
Partition the vertices of G into subsets S_i as follows.
Let S₀ consist of all vertices unmatched by M.
For integer j ≥ 0, let S_2j+1 be the set of vertices that:

1. Are adjacent to vertices in S_2j via some edge e ∈ E \ M.
2. Have not been included in any previously-defined set S_k, where k < j.

Each vertex v ∈ S_2j+1 must be adjacent to another vertex u via an edge e ∈ M
(otherwise, v is unmatched by M and would have been placed in S₀).
If the u has not yet been included in a set S_i, insert u in S_2j+2.
If there are no vertices adjacent to S_2j,
arbitrarily pick an unused vertex and continue in S_2j+1.

The illustration is an isomorphic partitioning of the example graph and its matching.

Each vertex in S_i has an edge to a vertex in S_i−1.
An alternating path can be formed from a given vertex, going up one level at a time, ending either at an unmatched vertex or at a level containing a single (matched) vertex.

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 edge uv.
There cannot be any edges in M between vertices in an even level subset S_2j,
because each of the vertices is connected by its single matched edge to a vertex in the previous level.
This path cannot have any repeated vertices since G is bipartite, so the start and end vertices must be distinct.

Now confirm that M is a maximum matching:

1. If both the start and end vertices of an alternating path are unmatched, the path contains one more edge in M than in E \ M. Swap the matched and unmatched edges. This gives a larger M, so M cannot be a maximum matching.
2. If there exists an unmatched edge uv between two vertices u and v in the same even-level subset S₂j, uv can be inserted in M to create a larger M because u and v were unmatched. Then M is also not a maximum matching.

Thus, if M is maximum, each edge in M has a single endpoint in an odd-level subsets S_2j+1,
and each edge in E \ M has at least one endpoint in an odd-level subset S_2j+1.
The union of the odd-level subsets forms a vertex cover of size |M|.
Since no smaller set of vertices could cover every edge in M, it must be a minimum vertex cover.

Therefore, a bipartite graph G with maximum matching M and minimum vertex cover C satisfies |M| = |C|.

Connections with perfect graphs

A graph is said to be perfect

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

 if, in every induced subgraph, the chromatic number equals the size of the largest clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

. 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 Line Coloring Theorem to a different class of perfect graphs, the line graph

Line graph

In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

s 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. Now König's Line Coloring Theorem, stating that the chromatic index equals the maximum vertex degree in any bipartite graph, can be interpreted as stating that the 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.