View source for Kőnig's theorem (graph theory)

{{Short description|Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs}}
{{About||the theorem about infinite graphs|Kőnig's lemma||König's theorem (disambiguation)}}
[[File:Koenigs-theorem-graph.svg|thumb|An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six.]]
In the [[mathematics|mathematical]] area of [[graph theory]], '''Kőnig's theorem''', proved by {{harvs|first=Dénes|last=Kőnig|authorlink=Dénes Kőnig|year=1931|txt}}, describes an equivalence between the [[maximum matching]] problem and the minimum [[vertex cover problem]] in [[bipartite graph]]s. It was discovered independently, also in 1931, by [[Jenő Egerváry]] in the more general case of [[weighted graph]]s.

== Setting ==
A [[vertex cover]] in a graph is a set of vertices that includes at least one endpoint of every edge, and a vertex cover is ''minimum'' if no other vertex cover has fewer vertices.<ref>Called a ''covering'' and a ''minimum covering'' respectively by {{harvtxt|Bondy|Murty|1976}}, p.&nbsp;73.</ref> A [[matching (graph theory)|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.<ref>{{harvtxt|Bondy|Murty|1976}}, p.&nbsp;70.</ref>

It is obvious from the definition that any vertex-cover set must be at least as large as any matching set (since for every edge in the matching, at least one vertex is needed in the cover). In particular, the [[minimum vertex cover]] set is at least as large as the [[maximum matching]] set. Kőnig's theorem states that, in any [[bipartite graph]], the minimum vertex cover set and the maximum matching set have in fact the same size.<ref name="thm-stmt">{{harvtxt|Bondy|Murty|1976}}, Theorem&nbsp;5.3, p.&nbsp;74; {{harvtxt|Cook|Cunningham|Pulleyblank|Schrijver|2011}}.</ref>

== Statement of the theorem ==
<blockquote>''In any [[bipartite graph]], the number of edges in a [[maximum matching]] equals the number of vertices in a [[minimum vertex cover]].<ref name="thm-stmt" />''</blockquote>

=== 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 (as well as of every other 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.

== Proofs ==

=== Constructive proof ===
[[File:Minimum cut in a bipartite graph.svg|thumb|Minimum cut <math>(S, T)</math> in the flow network <math>G'_\infty</math>]]
The following proof provides a way of constructing a minimum vertex cover from a maximum matching. Let <math>G=(V,E)</math> be a bipartite graph and let <math>A,B</math> be the two parts of the vertex set <math>V</math>.  Suppose that <math>M</math> is a maximum matching for <math>G</math>.

Construct the [[flow network]] <math>G'_\infty</math> derived from <math>G</math> in such way that there are edges of capacity <math>1</math> from the source <math>s</math> to every vertex <math>a \in A</math> and from every vertex <math>b \in B</math> to the sink <math>t</math>, and of capacity <math>+\infty</math> from <math>a</math> to <math>b</math> for any <math>(a, b) \in E</math>.

The size <math>|M|</math> of the maximum matching in <math>G</math> is the size of a [[Maximum flow problem|maximum flow]] in <math>G'_\infty</math>, which, in turn, is the size of a [[minimum cut]] in the network <math>G'_\infty</math>, as follows from the [[max-flow min-cut theorem]].

Let <math>(S, T)</math> be a minimum cut. Let <math>A = A_S \cup A_T</math> and <math>B = B_S \cup B_T</math>, such that <math>A_S, B_S \subset S</math> and <math>A_T, B_T \subset T</math>. Then the minimum cut is composed only of edges going from <math>s</math> to <math>A_T</math> or from <math>B_S</math> to <math>t</math>, as any edge from <math>A_S</math> to <math>B_T</math> would make the size of the cut infinite.

Therefore, the size of the minimum cut is equal to <math>|A_T|+|B_S|</math>. On the other hand, <math>A_T \cup B_S</math> is a vertex cover, as any edge that is not incident to vertices from <math>A_T</math> and <math>B_S</math> must be incident to a pair of vertices from <math>A_S</math> and <math>B_T</math>, which would contradict the fact that there are no edges between <math>A_S</math> and <math>B_T</math>.

Thus, <math>A_T \cup B_S</math> is a minimum vertex cover of <math>G</math>.{{sfnp|Cesa-Bianchi|2020}}

=== Constructive proof without flow concepts ===
No vertex in a vertex cover can cover more than one edge of <math>M</math> (because the edge half-overlap would prevent <math>M</math> from being a matching in the first place), so if a vertex cover with <math>|M|</math> vertices can be constructed, it must be a minimum cover.<ref>{{harvtxt|Bondy|Murty|1976}}, Lemma 5.3, p.&nbsp;74.</ref>

To construct such a cover, let <math>U</math> be the set of unmatched vertices in <math>A</math> (possibly empty), and let <math>Z</math> be the set of vertices that are either in <math>U</math> or are connected to <math>U</math> by alternating paths (paths that alternate between edges that are in the matching and edges that are not in the matching). Let
:<math>K=(A\setminus Z)\cup (B\cap Z).</math>
Every edge <math>e</math> in <math>E</math> either belongs to an alternating path (and has a right endpoint in <math>K</math>), or it has a left endpoint in <math>K</math>. For, if <math>e</math> is matched but not in an alternating path, then its left endpoint cannot be in an alternating path (because two matched edges can not share a vertex) and thus belongs to <math>A\setminus Z</math>. Alternatively, if <math>e</math> is unmatched but not in an alternating path, then its left endpoint cannot be in an alternating path, for such a path could be extended by adding <math>e</math> to it. Thus, <math>K</math> forms a vertex cover.<ref name="bm-proof">{{harvtxt|Bondy|Murty|1976}}, pp.&nbsp;74–75.</ref>

Additionally, every vertex in <math>K</math> is an endpoint of a matched edge.
For, every vertex in <math>A\setminus Z</math> is matched because <math>Z</math> is a superset of <math>U</math>, the set of unmatched left vertices.
And every vertex in <math>B\cap Z</math> must also be matched, for if there existed an alternating path to an unmatched vertex then changing the matching by removing the matched edges from this path and adding the unmatched edges in their place would increase the size of the matching. However, no matched edge can have both of its endpoints in <math>K</math>. Thus, <math>K</math> is a vertex cover of cardinality equal to <math>M</math>, and must be a minimum vertex cover.<ref name="bm-proof" />

=== Proof using linear programming duality ===
To explain this proof, we first have to extend the notion of a matching to that of a [[fractional matching]] - an assignment of a weight in [0,1] to each edge, such that the sum of weights near each vertex is at most 1 (an integral matching is a special case of a fractional matching in which the weights are in {0,1}).  Similarly we define a fractional vertex-cover - an assignment of a non-negative weight to each vertex, such that the sum of weights in each edge is at least 1 (an integral vertex-cover is a special case of a fractional vertex-cover in which the weights are in {0,1}).

The maximum fractional matching size in a graph <math>G=(V,E)</math> is the solution of the following [[linear program]]:<blockquote>Maximize      '''1'''<sub>''E''</sub> ''·'' '''x'''

Subject to:     '''x''' ≥ '''0'''''<sub>E</sub>''

__________  '''A'''<sub>''G''</sub> · '''x'''  ''≤  '''1'''<sub>V</sub>.''</blockquote>where '''x''' is a vector of size |''E''| in which each element represents the weight of an edge in the fractional matching.  '''1'''<sub>E</sub> is a vector of |''E''| ones, so the first line indicates the size of the matching. '''0'''''<sub>E</sub>'' is a vector of |''E''| zeros, so the second line indicates the constraint that the weights are non-negative. '''1'''<sub>V</sub> is a vector of |''V''| ones and '''A'''<sub>''G''</sub> is the [[incidence matrix]] of ''G,'' so the third line indicates the constraint that the sum of weights near each vertex is at most 1.

Similarly, the minimum fractional vertex-cover size in <math>G=(V,E)</math> is the solution of the following LP:<blockquote>Minimize      '''1'''<sub>''V''</sub> ''·'' '''y'''

Subject to:     '''y''' ≥ '''0'''''<sub>V</sub>''

__________  '''A'''<sub>''G''</sub><sup>T</sup> · '''y'''  ≥  '''''1'''<sub>E</sub>.''</blockquote>where '''y''' is a vector of size |V| in which each element represents the weight of a vertex in the fractional cover. Here, the first line is the size of the cover, the second line represents the non-negativity of the weights, and the third line represents the requirement that the sum of weights near each edge must be at least 1.

Now, the minimum fractional cover LP is exactly the [[dual linear program]] of the maximum fractional matching LP. Therefore, by the LP duality theorem, both programs have the same solution. This fact is true not only in bipartite graphs but in arbitrary graphs:<blockquote>''In any graph, the largest size of a fractional matching equals the smallest size of a fractional vertex cover.''</blockquote>What makes bipartite graphs special is that, in bipartite graphs, both these linear programs have optimal solutions in which all variable values are integers. This follows from the fact that in the [[Matching polytope|fractional matching polytope]] of a bipartite graph, all extreme points have only integer coordinates, and the same is true for the fractional vertex-cover polytope. Therefore the above theorem implies:{{sfnp|Lovász|Plummer|1986|p=270}}
<blockquote>''In any bipartite graph, the largest size of a matching equals the smallest size of a vertex cover.''</blockquote>

==Algorithm==
The constructive proof described above provides an algorithm for producing a minimum vertex cover given a maximum matching.  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.<ref>For this algorithm, see {{harvtxt|Storer|2001}}, p&nbsp;319, and for the connection to vertex cover see p.&nbsp;342.</ref>

Despite the equivalence of the two problems from the point of view of exact solutions, they are not equivalent for [[approximation algorithm]]s. Bipartite maximum matchings can be approximated arbitrarily accurately in constant time by [[distributed algorithm]]s; in contrast, approximating the minimum vertex cover of a bipartite graph requires at least logarithmic time.{{sfnp|Göös|Suomela|2014}}

===Example===
In the graph shown in the introduction take <math>L</math> to be the set of vertices in the bottom layer of the diagram and <math>R</math> to be the set of vertices in the top layer of the diagram. From left to right label the vertices in the bottom layer with the numbers 1, …, 7 and label the vertices in the top layer with the numbers 8, …, 14. The set <math>U</math> of unmatched vertices from <math>L</math> is {1}. The alternating paths starting from <math>U</math> are 1–10–3–13–7, 1–10–3–11–5–13–7, 1–11–5–13–7, 1–11–5–10–3–13–7, and all subpaths of these starting from 1. The set <math>Z</math> is therefore {1,3,5,7,10,11,13}, resulting in <math>L\setminus Z=\{2,4,6\}</math>, <math>R\cap Z=\{10,11,13\}</math> and the minimum vertex  cover <math>K=\{2,4,6,10,11,13\}</math>.

== Non-bipartite graphs ==
For graphs that are not bipartite, the minimum vertex cover may be larger than the maximum matching. Moreover, the two 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 (graph theory)|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.<ref name="s342">{{harvtxt|Storer|2001}},  [https://books.google.com/books?id=S-tXjl1hsUYC&pg=PA342 Exercise&nbsp;261, p.&nbsp;342].</ref>

== History ==
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 graph|regular]] bipartite graph has a [[perfect matching]],<ref>In a poster displayed at the 1998 [[International Congress of Mathematicians]] 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 [[projective configuration|configurations]] in the 1894 thesis of [[Ernst Steinitz]].</ref> 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 [[degree (graph theory)|maximum degree]]<ref>{{harvtxt|Biggs|Lloyd|Wilson|1976}}.</ref> – the latter statement is known as '''Kőnig's line coloring theorem'''.{{sfnp|Lovász|Plummer|1986|loc=Theorem 1.4.17, pp. 37ff.}} However, {{harvtxt|Bondy|Murty|1976}} attribute Kőnig's theorem itself to a later paper of Kőnig (1931).

According to {{harvtxt|Biggs|Lloyd|Wilson|1976}}, Kőnig attributed the idea of studying matchings in bipartite graphs to his father, mathematician [[Gyula Kőnig]]. In Hungarian, Kőnig's name has a [[double acute accent]], but his theorem is sometimes spelled (incorrectly) in German characters, with an [[Umlaut (diacritic)|umlaut]].

== Related theorems ==
Kőnig's theorem is equivalent to many 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 [[Maximum flow problem|maximum flow]], the theorem also results from the [[max-flow min-cut theorem]].{{sfnp|Cook|Cunningham|Pulleyblank|Schrijver|2011}}

== Connections with perfect graphs ==
A graph is said to be [[perfect graph|perfect]] if, in every [[induced subgraph]], the [[chromatic number]] equals the size of the largest [[clique (graph theory)|clique]]. Any bipartite graph is perfect,<ref>"Trivially", according to {{harvtxt|Lovász|1974}}.</ref> 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,<ref>This is the [[perfect graph theorem]] of {{harvtxt|Lovász|1972}}</ref> 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 {{harvtxt|Gallai|1958}}.

One can also connect Kőnig's line coloring theorem to a different class of perfect graphs, the [[line graph]]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.{{sfnp|Lovász|1974}}

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.{{sfnp|Lovász|1974}}

== Weighted variants ==
Konig's theorem can be extended to [[weighted graph]]s.

=== [[Jenő Egerváry|Egerváry]]'s theorem for edge-weighted graphs ===
[[Jenő Egerváry]] (1931) considered graphs in which each edge ''e'' has a non-negative integer weight ''w<sub>e</sub>''. The weight vector is denoted by '''w'''. The '''w-'''''weight of a matching'' is the sum of weights of the edges participating in the matching. A '''''w-'''vertex-cover'' is a multiset of vertices ("multiset" means that each vertex may appear several times), in which each edge ''e'' is adjacent to at least ''w<sub>e</sub>'' vertices. [[Jenő Egerváry|Egerváry]]'s theorem says:<blockquote>''In any edge-weighted bipartite graph, the maximum '''w-'''weight of a matching equals the smallest number of vertices in a '''w-'''vertex-cover.''</blockquote>The maximum '''''w-'''''weight of a fractional matching is given by the LP:{{sfnp|Lovász|Plummer|1986|p=271}}
<blockquote>Maximize      '''''w''''' ''·'' '''x'''

Subject to:     '''x''' ≥ '''0'''''<sub>E</sub>''

__________  '''A'''<sub>''G''</sub> · '''x'''  ''≤  '''1'''<sub>V</sub>.''</blockquote>And the minimum number of vertices in a fractional '''''w-'''''vertex-cover is given by the dual LP:<blockquote>Minimize      '''1'''<sub>''V''</sub> ''·'' '''y'''

Subject to:     '''y''' ≥ '''0'''''<sub>V</sub>''

__________  '''A'''<sub>''G''</sub><sup>T</sup> · '''y'''  ≥  '''''w'''.''</blockquote>As in the proof of Konig's theorem, the LP duality theorem implies that the optimal values are equal (for any graph), and the fact that the graph is bipartite implies that these programs have optimal solutions in which all values are integers.

=== Theorem for vertex-weighted graphs ===
One can consider a graph in which each vertex ''v'' has a non-negative integer weight ''b<sub>v</sub>''. The weight vector is denoted by '''b'''. The '''''b'''-weight'' of a vertex-cover is the sum of ''b<sub>v</sub>'' for all ''v'' in the cover. A '''''b'''-matching'' is an assignment of a non-negative integral weight to each edge, such that the sum of weights of edges adjacent to any vertex ''v'' is at most ''b<sub>v</sub>''. Egerváry's theorem can be extended, using a similar argument, to graphs that have both edge-weights '''w''' and vertex-weights '''b''':{{sfnp|Lovász|Plummer|1986|p=271}}
<blockquote>''In any edge-weighted vertex-weighted bipartite graph, the maximum '''w-'''weight of a '''b'''-matching equals the minimum '''b'''-weight of vertices in a '''w-'''vertex-cover.''</blockquote>

== See also ==

* [[Matching_in_hypergraphs#Kőnig's_property|Kőnig's property in hypergraphs]]

== Notes ==
{{reflist|30em}}

== References ==
{{sfn whitelist |CITEREFLovászPlummer1986}}
*{{citation
 | last1 = Biggs | first1 = E. K.
 | last2 = Lloyd
 | last3 = Wilson | first3 = R. J.
 | isbn = 0-19-853916-9
 | pages = 203–207
 | publisher = Oxford University Press
 | title = Graph Theory 1736–1936
 | title-link = Graph Theory, 1736–1936
 | year = 1976}}.
*{{citation |last=Cesa-Bianchi |first=Nicolò |author-link=Nicolò Cesa-Bianchi |date=April 11, 2020 |title=Matchings and the max-flow min-cut theorem |url=https://cesa-bianchi.di.unimi.it/GraphTheory/Notes/matchings.pdf |access-date=}}
*{{citation
 | last1 = Cook | first1 = William J. | author1-link = William J. Cook
 | last2 = Cunningham | first2 = William H.
 | last3 = Pulleyblank | first3 = William R. | author3-link = William R. Pulleyblank
 | last4 = Schrijver | first4 = Alexander | author4-link = Alexander Schrijver
 | isbn = 9781118031391
 | pages = 48–49
 | publisher = John Wiley & Sons
 | series = Wiley Series in Discrete Mathematics and Optimization
 | title = Combinatorial Optimization
 | url = https://books.google.com/books?id=tarLTNwM3gEC&pg=PA48
 | volume = 33
 | year = 2011}}.
*{{citation
 | last1 = Bondy
 | first1 = J. A.
 | author1-link = J. A. Bondy
 | last2 = Murty
 | first2 = U. S. R.
 | author2-link = U. S. R. Murty
 | isbn = 0-444-19451-7
 | publisher = North Holland
 | title = Graph Theory with Applications
 | year = 1976
 | url-access = registration
 | url = https://archive.org/details/graphtheorywitha0000bond
 }}.
*{{citation
 | last = Gallai | first = Tibor | author-link = Tibor Gallai
 | doi = 10.1007/BF02020271 | doi-access = 
 | issue = 3–4
 | journal = [[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]
 | mr = 0124238
 | pages = 395–434
 | title = Maximum-minimum Sätze über Graphen
 | volume = 9
 | year = 1958}}.
*{{citation
 | last1 = Göös | first1 = Mika
 | last2 = Suomela | first2 = Jukka
 | arxiv = 1205.4605
 | doi = 10.1007/s00446-013-0194-z
 | issue = 6
 | journal = Distributed Computing
 | mr = 3280546
 | pages = 435–443
 | title = No sublogarithmic-time approximation scheme for bipartite vertex cover
 | volume = 27
 | year = 2014| s2cid = 13513566
 }}
*{{citation
 | last = Kőnig | first = Dénes | author-link = Dénes Kőnig
 | journal = Matematikai és Természettudományi Értesítő
 | pages = 104–119
 | title = Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére
 | volume = 34
 | year = 1916}}.
*{{citation
 | last = Kőnig | first = Dénes | author-link = Dénes Kőnig
 | journal = Matematikai és Fizikai Lapok
 | pages = 116–119
 | title = Gráfok és mátrixok
 | volume = 38
 | year = 1931}}.
*{{citation
 | last = Lovász | first = László | author-link = László Lovász
 | doi = 10.1016/0012-365X(72)90006-4
 | issue = 3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 0302480
 | pages = 253–267
 | title = Normal hypergraphs and the perfect graph conjecture
 | volume = 2
 | year = 1972| doi-access = 
 }}.
*{{citation
 | last = Lovász | first = László | author-link = László Lovász
 | contribution = Minimax theorems for hypergraphs
 | doi = 10.1007/BFb0066186 | doi-access = 
 | location = Berlin
 | mr = 0406862
 | pages = 111–126
 | series=Lecture Notes in Mathematics
 | volume=411
 | publisher = Springer
 | isbn = 978-3-540-06846-4 | title = Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross)
 | year = 1974}}.
*{{Cite Lovasz Plummer}}
*{{citation
 | last = Storer | first = J. A.
 | isbn = 9780817642532
 | publisher = Springer
 | series = Progress in Computer Science and Applied Logic Series
 | title = An Introduction to Data Structures and Algorithms
 | year = 2001}}.

{{DEFAULTSORT:Koenigs theorem}}
[[Category:Theorems in graph theory]]
[[Category:Articles containing proofs]]
[[Category:Perfect graphs]]
[[Category:Matching (graph theory)]]
[[Category:Bipartite graphs]]