For the degree-constrained linear programming relaxation of a matching in a graph, retain precisely the edges with fractional coordinates. In a bipartite graph, an even graph cycle in this subgraph permits alternating positive and negative perturbations preserving all vertex sums. If the subgraph is a forest, use a graph path between two tree leaves: its endpoints have positive slack and its internal sums remain unchanged. Either perturbation expresses the original feasible point as the midpoint of two distinct feasible points. Hence a fractional feasible point cannot be an extreme point, proving integrality of all extreme points of the bipartite degree relaxation.
Articles by others on the same topic
There are currently no matching articles.