Let be a matrix; that is, a matrix where each of whose entries is either a 0 or a 1. A line in is either a row or a column of . Use Konig's theroem to prove that the minimum number of lines containing all the 1's of is equal to the maximum number of 1's, no two of which are in the same line.
Let be a bipartite graph with vertex bipartition , such that is an adjacency matrix of graph , where is a set of vertices corresponding to the rows of matrix , and is the vertex set corresponding to the columns. So the result follows from Konig's thereom. I am not sure how the adjacency matrix helps for making this bipartition. I would like some help on this one. Thanks in advance.