Fractional matchings and the Edmonds-Gallai theorem

AbstractA fractional matching of a graph G = (V, E) is an assignment of the values 0, 12, 1 to the edges of G in such a way that for each node, the sum of the values on the incident edges is at most 1. We show how the Edmonds-Gallai structure theorem for matchings in graphs can be applied to two different classes of maximum fractional matchings. The first, introduced by Uhry [16], is the class of maximum fractional matchings for which the number of cycles in the support is minimized. The second, introduced by Mühlbacher et al. [12] is the class of maximum fractional matchings for which the number of edges assigned the value 1 is maximized