Total dual integrality of matching forest constraints

Let G=(V, E, A) be a mixed graph. That is, (V E) is an undirected graph and (V, A) is a directed graph. A matching forest (introduced by R. Giles) is a subset F of E boolean ORA s uch that F contains no circuit (in the underlying undirected graph) and suc h that for each nu is an element ofV there is at most one e is an element o f F such that nu is head of e. (For an undirected edge e, both ends of e ar e called head of e.) Giles gave a polynomial-time algorithm to find a maximum-weight matching fo rest, yielding as a by-product a characterization of the inequalities deter mining the convex hull of the incidence vectors of the matching forests. We prove that these inequalities form a totally dual integral system. It is equivalent to an "all-integer" min-max relation for the maximum weight of a matching forest. Our proof is based on an exchange property for matching forests, and implies Giles' characterization.