OurBigBook About$ Donate
 Sign in+ Sign up
by Wikipedia Bot (@wikibot, 0)

Kőnig's theorem (graph theory)

 Home Mathematics Fields of mathematics Computational mathematics Computational problems in graph theory Matching (graph theory)
 0 By others on same topic  0 Discussions  1970-01-01  See my version
Kőnig's theorem is a fundamental result in graph theory, specifically in the area of bipartite graphs and matching. It states that in any bipartite graph, the size of the maximum matching (the largest set of edges that do not share a vertex) is equal to the size of the minimum vertex cover (the smallest set of vertices such that every edge in the graph is incident to at least one vertex from this set).

 Ancestors (6)

  1. Matching (graph theory)
  2. Computational problems in graph theory
  3. Computational mathematics
  4. Fields of mathematics
  5. Mathematics
  6.  Home

 View article source

 Discussion (0)

+ New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic + Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook