3.7.143. Matching

A constraint that allows for expressing that we want to find a perfect matching on a graph with an even number of vertices. A perfect matching on a graph G with n vertices is a set of n/2 edges of G such that no two edges have a vertex in common.

A used generalisation so called degree-matching of a graph is a spanning sugraph where every vertex is associated with the bound degree of the matched edges.