# Difference between revisions of "König theorem"

If the entries of a rectangular matrix are zeros and ones, then the minimum number of lines containing all ones is equal to the maximum number of ones that can be chosen so that no two of them lie on the same line. (Here the term "line" denotes either a row or a column in the matrix.) The theorem was formulated and proved by D. König [1]. It is one of the basic theorems in combinatorics and is the matrix analogue of Hall's criterion for the existence of a system of distinct representatives of a family of subsets of a finite set (see Selection theorems). There is also a widespread statement of König's theorem in terms of graphs: In a bipartite graph (cf. Graph, bipartite) the number of edges in a maximal matching is equal to the number of elements of a minimal vertex covering.

König's theorem is often used in various combinatorial questions relating to selection and extremal problems. A generalization to the case of infinite matrices is known [3].

#### References

 [1] D. König, "Graphs and matrices" Mat. Lapok , 38 (1931) pp. 116–119 (In Hungarian) [2] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9 [3] M. Lewin, "Essential coverings of a matrix" Proc. Cambridge Philos. Soc. , 67 (1970) pp. 263–267