Therefore, a maximum cardinality matching in G is given by the following integer linear program: Maximize 1E · x Subject to: x in {0,1}m
The fractional matching polytope of a graph G, denoted FMP(G), is the polytope defined by the relaxation of the above linear program, in which each x may be a fraction and not just an integer:Maximize 1E · x Subject to: x ≥ 0E
For example, in the triangle graph there are 3 edges, and the corresponding linear program has the following 6 constraints: Maximize x1+x2+x3 Subject to: x1≥0, x2≥0, x3≥0.
__________ x1+x2≤1, x2+x3≤1, x3+x1≤1.This set of inequalities represents a polytope in R3 - the 3-dimensional Euclidean space.
The above example is a special case of the following general theorem:[1]: 274 G is a bipartite graph if-and-only-if MP(G) = FMP(G) if-and-only-if all corners of FMP(G) have only integer coordinates.This theorem can be proved in several ways.
When G is bipartite, its incidence matrix AG is totally unimodular - every square submatrix of it has determinant 0, +1 or −1.
Each corner of FMP(G) satisfies a set of m linearly-independent inequalities with equality.
Therefore, to calculate the corner coordinates we have to solve a system of equations defined by a square submatrix of AG.
By Cramer's rule, the solution is a rational number in which the denominator is the determinant of this submatrix.
The perfect matching polytope of a graph G, denoted PMP(G), is a polytope whose corners are the incidence vectors of the integral perfect matchings in G.[1]: 274 Obviously, PMP(G) is contained in MP(G); In fact, PMP(G) is the face of MP(G) determined by the equality:1E · x = n/2.Edmonds[3] proved that, for every graph G, PMP(G) can be described by the following constraints:1E(v) · x = 1 for all v in V (-- exactly one edge adjacent to v is in the matching) 1E(W) · x ≥ 1 for every subset W of V with |W| odd (-- at least one edge should connect W to V\W).
[4]: 206 By solving algorithmic problems on convex sets, one can find a minimum-weight perfect matching.