The König-Egeváry theorem, sometimes simply called König's theorem, asserts that the matching number (i.e., size of
a maximum independent edge set ) is
equal to the vertex cover number (i.e., size
of a minimum vertex cover ) for a bipartite
graph .
More generally, the theorem states that the maximum size of a partial matching in a relation equals the minimum size of a separating set.
See also Bipartite Graph ,
Frobenius-König Theorem ,
König's Line Coloring
Theorem ,
König's Theorem ,
Matching
Number ,
Maximum Independent Edge Set ,
Minimum Vertex Cover ,
Separating
Family ,
Vertex Cover Number
Explore with Wolfram|Alpha
References Deming, R. W. "Independence Numbers of Graphs--An Extension of the Koenig-Egervary Theorem." Disc. Math. 27 , 23-33,
1979. Kung, J. P. S. "Jacobi's Identity and the König-Egerváry
Theorem." Disc. Math. 49 , 75-77, 1984. Referenced on
Wolfram|Alpha König-Egeváry
Theorem
Cite this as:
Weisstein, Eric W. "König-Egeváry Theorem." From MathWorld https://mathworld.wolfram.com/Koenig-EgevaryTheorem.html
Subject classifications
