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,

\\begin{bmatrix}1&0&0&0&0&1\\\\1&0&0&0&0&1\\\\0&1&0&0&0&1\\\\0&1&0&0&0&1\\\\1&0&1&1&1&0\\\\\\end{bmatrix}

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

References

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. PureAppl. Math. 22(11) (1991): 905 - 911