Total dual integrality of matching forest constraints (Q5932756)

A matching forest in a mixed graph (that is, where some of the edges are oriented) has no circuit in the underlying undirected graph and each vertex has indegree at most one (counting heads of the directed edges and either end of the undirected edges). ``Giles gave a polynomial time algorithm to find a maximum weight matching forest, yielding as a by-product a characterization of the inequalities determining the convex hull of the incidence vectors of the matching forests.'' The author proves that these inequalities form a totally dual integral system.