# 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. Pure Appl. Math. 22(11) (1991): 905 - 911
Title König-Egervary theorem KonigEgervaryTheorem 2013-03-22 16:33:47 2013-03-22 16:33:47 PrimeFan (13766) PrimeFan (13766) 4 PrimeFan (13766) Definition msc 05A19 Konig-Egervary theorem