x ≤ 1V.And the minimum number of vertices in a fractional w-vertex-cover is given by the dual LP:Minimize 1V · y Subject to: y ≥ 0V __ AGT · y ≥ w.As in the proof of Konig's theorem, the LP duality theorem implies that the optimal values are equal (for any graph), and the fact that the graph is bipartite implies that these programs have optimal solutions in which all values are integers. Theorem for vertex-weighted graphs One can consider a graph in which each vertex v has a non-negative integer weight bv. The weight vector is denoted by b. The b-weight of a vertex-cover is the sum of bv for all v in the cover. A b-matching is an assignment of a non-negative integral weight to each edge, such that the sum of weights of edges adjacent to any vertex v is at most bv. Egervary's theorem can be extended, using a similar argument, to graphs that have both edge-weights w and vertex-weights b:In any edge-weighted vertex-weighted bipartite graph, the maximum w-weight of a b-matching equals the minimum b-weight of vertices in a w-vertex-cover. See also Kőnig's property in hypergraphs Notes References . . . . . . . . . Theorems in graph theory Articles containing proofs Perfect graphs Matching (graph theory) Bipartite graphs