A combinatoric interpretation of dual variables for weighted matching and f-factors

The linear program dual variables for weighted matching and its generalization to f-factors are shown to be the weights of certain subgraphs: y duals are the weights of certain maximum matchings or f-factors; z duals are the weights of certain 2-factors or 2f-factors. Similar interpretations have been given for the bipartite case of these problems, where only y duals occur, but our variant is included here for completeness. In all cases the y duals are canonical in a well-defined sense; z duals are canonical for matching and more generally for b-matchings (a special case of f-factors) but for f-factors their support can vary. As weights of combinatoric objects the duals are integral for given integral edge weights, and so they give new proofs that the linear programs for these problems are TDI.