Kőnig's theorem

GPTKB entity

Statements (16)
Predicate Object
gptkbp:instanceOf gptkb:mathematical_concept
gptkbp:appliesTo bipartite graphs
gptkbp:field graph theory
gptkbp:generalizes gptkb:Kőnig–Egerváry_theorem
https://www.w3.org/2000/01/rdf-schema#label Kőnig's theorem
gptkbp:namedAfter gptkb:Dénes_Kőnig
gptkbp:publicationYear 1931
gptkbp:publishedIn gptkb:Mathematische_Annalen
gptkbp:relatedTo gptkb:Hall's_marriage_theorem
maximum matching
minimum vertex cover
gptkbp:sentence In any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover.
gptkbp:usedIn theoretical computer science
combinatorics
gptkbp:bfsParent gptkb:Gyula_Kőnig
gptkbp:bfsLayer 6