On a Min-Max Theorem of Cacti

A simple proof is presented for the min-max theorem of Lov'asz on cacti. Instead of using the result of Lov'asz on matroid parity, we shall apply twice the (conceptionally simpler) matroid intersection theorem. 1 Introduction The graph matching problem and the matroid intersection problem are two well-solved problems in Combinatorial Theory in the sense of min-max theorems and polynomial algorithms for finding an optimal solution. The matroid parity problem, a common generalization of them, turned out to be much more difficult. For the general problem there does not exist polynomial algorithm [2], [3]. Moreover, it contains NP-complete problems. On the other hand, for linear matroids Lov'asz [3] provided a min-max formula and a polynomial algorithm. There are several earlier results which can be derived from Lov'asz' theorem, e.g. Tutte's result on f-factors [8], a result of Mader on openly disjoint A-paths [5], a result of Nebesky concerning maximum genus of graphs [6]. Another appli..