unmatched vertex then changing the matching by removing the matched edges from this path and adding the unmatched edges in their place would increase the size of the matching. However, no matched edge can have both of its endpoints in . Thus, is a vertex cover of cardinality equal to , and must be a minimum vertex cover. Proof using linear programming duality To explain this proof, we first have to extend the notion of a matching to that of a fractional matching - an assignment of a weight in [0,1] to each edge, such that the sum of weights near each vertex is at most 1 (an integral matching is a special case of a fractional matching in which the weights are in {0,1}). Similarly we define a fractional vertex-cover - an assignment of a non-negative weight to each vertex, such that the sum of weights in each edge is at least 1 (an integral vertex-cover is a special case of a fractional vertex-cover in which the weights are in {0,1}). The maximum fractional matching size in a graph is the solution of the following linear program:Maximize 1E · x Subject to: x ≥ 0E __ AG · x ≤ 1V.where x is a vector of size |E| in which each element represents the weight of an edge in the fractional matching. 1E is a vector of |E| ones, so the first line indicates the size of the matching. 0E is a vector of |E| zeros, so the second line indicates the constraint that the weights are non-negative. 1V is a vector of |V| ones and AG is the incidence matrix of G, so the third line indicates the constraint that the sum of weights near each vertex is at most 1. Similarly, the minimum fractional vertex-cover size in is the solution of the following LP:Minimize 1V · y Subject to: y ≥ 0V __ AGT · y ≥ 1E.where y is a vector of size |V| in which each element represents the weight of a vertex in the fractional cover. Here, the first line is the size of the cover, the second line represents the non-negativity of the weights, and the third line represents the requirement that the sum of weights near each edge must be at least 1. Now, the minimum fractional cover LP is exactly the dual linear program of the maximum fractional matching LP. Therefore,