Abstract. It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of the extended polymatroid associated with the submodular function defined on subsets of the vertex set. Based on this fact, different algorithms for testing flow feasibility can be used to find some perfect matching in a given graph.

Keywords: perfect matching, graph, extended polymatroid.