# König's Theorem (graph theory)

The set of King is a mathematical theorem from graph theory , which for bipartite graphs a relationship between a greatest pairing and a minimum vertex cover shows. It reads:

In a bipartite graph, the size of a largest pairing is equal to the size of a minimum node coverage.

The theorem is named after the Hungarian mathematician Dénes Kőnig , who proved it in 1931. Independently of König, the mathematician Jenő Egerváry , also in 1931, proved a more general formulation of the theorem for weighted graphs . That is why the sentence is sometimes referred to as König and Egerváry's sentence.

## example

An example of a bipartite graph, with the greatest pairing (blue) and the minimum vertex coverage (red):

## algorithm

This algorithm describes how the minimum node coverage is obtained from a largest pairing. A largest pairing can be calculated, for example, using the Hopcroft and Karp algorithm. The two sets of nodes of the bipartite graph are denoted by (above) and (below). ${\ displaystyle O}$${\ displaystyle U}$

1. Calculate a largest match.
2. All nodes from not included in the pairing are inserted into.${\ displaystyle O}$${\ displaystyle T}$
3. We trace from these nodes to edges that are not included in the pairing . All visited nodes are inserted into.${\ displaystyle U}$${\ displaystyle T}$
4. From the nodes reached in this way , we go back to the edges contained in the pairing . All visited nodes are inserted into.${\ displaystyle U}$${\ displaystyle O}$${\ displaystyle T}$
5. Repeat the previous two steps until no more nodes are added.${\ displaystyle T}$
6. The minimum node overlap results from ${\ displaystyle (O \ setminus T) \ cup (U \ cap T)}$

## Variant for weighted graphs

Independently of König, the mathematician Jenő Egerváry proved a variant of the theorem for weighted graphs . Here we consider bipartite graphs with a weight function that assigns a nonnegative integer to each edge in the graph. A weighted vertex coverage of is a function that assigns a nonnegative integer to every vertex in the graph, so that applies to all edges . The weight of is given by. The sentence then reads as follows: ${\ displaystyle G = (V = A \ cup B, E)}$${\ displaystyle d \ colon E \ to \ mathbb {N}}$${\ displaystyle d}$${\ displaystyle \ pi \ colon V \ to \ mathbb {N}}$${\ displaystyle \ pi (u) + \ pi (v) \ geq d (\ {u, v \})}$${\ displaystyle \ {u, v \} \ in E}$${\ displaystyle \ pi}$${\ displaystyle \ sum _ {v \ in V} \ pi (v)}$

In a complete bipartite graph with and a weight function , the maximum weight of a pairing corresponds to the minimum weight of a weighted node cover of .${\ displaystyle G = (V = A \ cup B, E)}$${\ displaystyle | A | = | B |}$${\ displaystyle d \ colon E \ to \ mathbb {N}}$${\ displaystyle d}$

## Individual evidence

1. ^ Klaus Wagner: Graph theory. Bibliographisches Institut Hochschultaschenbücher, Mannheim 1970, ISBN 3-411-00248-4 , sentence 9.9
2. Jenő Egerváry: Matrixok kombinatorius tulajdonságairól . In: Matematikai és Fizikai Lapok . tape 38 , 1931, p. 16-28 . (On combinatorial properties of matrices)
3. a b Harold W. Kuhn: On combinatorial properties of matrices . In: George Washington University (Ed.): Logistics Papers . tape 11 , 1955, pp. 1-11 .