Combinatorics Matchings and covers Theorem
Kőnig's theorem
Builds on Bipartite graphMatchingVertex cover
Statement
Let be a finite bipartite graph. Then the largest number of edges in a matching of is equal to the smallest number of vertices in a vertex cover of .
Remarks
In every graph, a vertex cover has at least as many vertices as a matching has edges. Kőnig's theorem says that equality holds for bipartite graphs. The theorem fails for other graphs. The triangle has matchings with edge only, but each vertex cover has vertices.
History
Dénes Kőnig published the theorem in 1931. Jenő Egerváry found it independently in the same year, in a more general form with weights.
Reading path
To understand this page from the ground up, read these 4 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Bipartite graph definition
- Matching definition
- Vertex cover definition
- Kőnig's theorem statement
Where this leads
1 page builds on this one.
Further reading
- Web https://en.wikipedia.org/wiki/Kőnig's_theorem_(graph_theory), Statement of the theorem
About this page
| Tag | 0JP0ZF57PN |
|---|---|
| URI | m2://0JP0ZF57PN |
| Kind | statement, theorem |
| Writing | W1 stated |
| MSC | 05C70 |
| Status | This copy of the site has no build data. Run m2 status 0JP0ZF57PN. |
| Uses | Bipartite graph, Matching, Vertex cover |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge about out: the concepts that the statement is about (0 of 1)
- edge proves in: at least one proof node (0 of 1)
- edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
- explanation L2 (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.