Fractional matchings and the Edmonds-Gallai theorem (Q1098861): Difference between revisions

A fractional matching of a graph is an assignment of the values 0, 1/2, 1 to the edges of the graph in such a way that for each node, the sum of the values on the incident edges is at most 1. This note shows that the Edmonds-Gallai structure theorem for maximum matchings in graphs provides a structural characterization for the class of maximum fractional matchings for which the number of cycles in the support is minimum. This in turn provides an easy derivation for the class of maximum fractional matchings for which the number of edges assigned the value 1 is maximized.