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[edit]

Comments[edit]

A vertex covering or disconnecting set of a graph $G$ is a collection of vertices $C$ such that every edge $G$ is incident with a vertex from $C$ (i.e. the edges incident with a vertex from $C$ cover $G$). 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 $(0,1)$-matrix $A$ is equal to the minimum number of rows and columns which together cover all the 1's of $A$.

References[edit]