A tree version of Konig's theorem

Abstract

Konig's theorem states that the covering number and the matching number of a bipartite graph are equal. We prove a generalisation of this result, in which each point in one side of the graph is replaced by a subtree of a given tree. The proof uses a recent extension of Hall's theorem to families of hypergraphs, by the first author and P. Haxell.

6 pages, no figures. Submitted to Combinatorica. Minor mistakes in the proofs in v1 were corrected