König-Egeváry Theorem

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


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--A Wolfram Web Resource.

Subject classifications