König-Egervary theorem

The König-Egervary theorem states that in a finite matrix of 0’s and 1’s, the maximum numbers of 1’s such that no two are in a line, equals the minimum number of lines which collectively contain all the 1’s. Here line means row or column.

Take this matrix, for example,


Here the max and min numbers (always equal) are 4.


  • 1 A. Chandra Babu, P. V. Ramakrishnan, “New Proofs of Konig-Egervary Theorem And Maximal Flow-Minimal Cut Capacity Theorem Using O. R. Techniques” Indian J. Pure Appl. Math. 22(11) (1991): 905 - 911
Title König-Egervary theorem
Canonical name KonigEgervaryTheorem
Date of creation 2013-03-22 16:33:47
Last modified on 2013-03-22 16:33:47
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 4
Author PrimeFan (13766)
Entry type Definition
Classification msc 05A19
Synonym Konig-Egervary theorem