Extension of Hall's theorem and an algorithm for finding the (1, n)-complete matching

Vites Longani

Abstract

Hall's theorem provides the necessary and suffcient conditions for the existence of (1,1)-complete matching in bipartite graphs. The extension of Hall's theorem provides the necessary and suffcient conditions for the existence of (1,n)-complete matching, with $n \geq 1$. The proof of the extension exist in some few advanced texts with more advanced language, and therefore the extension is not widely known. In this paper we propose another approach of the proof which is simpler and less involved. Also, from this, an algorithm for finding the (1,n)-complete matching is derived.