= Fractional support graph of a matching relaxation
{title2=$H=(V,\{e:0<x_e<1\})$}
= Fractional support graph
{synonym}
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.
Back to article page
