View source for 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 [[#References|[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|Selection theorems]]). There is also a widespread statement of König's theorem in terms of graphs: In a bipartite graph (cf. [[Graph, bipartite|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 [[#References|[3]]].

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



====Comments====
A vertex covering or disconnecting set of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557701.png" /> is a collection of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557702.png" /> such that every edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557703.png" /> is incident with a vertex from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557704.png" /> (i.e. the edges incident with a vertex from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557705.png" /> cover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557706.png" />). 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557707.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557708.png" /> is equal to the minimum number of rows and columns which together cover all the 1's of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055770/k0557709.png" />.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.J. Wilson,   "Introduction to graph theory" , Longman  (1972)  pp. §27</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  Hj. Walther,   "Ten applications of graph theory" , Reidel  (1984)  pp. Sect. 6.1</TD></TR></table>