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

Comments

A vertex covering or disconnecting set of a graph is a collection of vertices such that every edge is incident with a vertex from (i.e. the edges incident with a vertex from cover ). A minimal vertex covering is a cut set.

The term rank of a matrix of zeros and ones is defined as the largest number of ones such that no two lie in the same row or column. Thus, König's theorem, also known as the König–Egerváry theorem, can also be formulated as: The term rank of a -matrix is equal to the minimum number of rows and columns which together cover all the 1's of .

References

[a1]	R.J. Wilson, "Introduction to graph theory" , Longman (1972) pp. §27
[a2]	Hj. Walther, "Ten applications of graph theory" , Reidel (1984) pp. Sect. 6.1