An effective version of Hall’s theorem
Henry A. Kiersteád · Proceedings of the American Mathematical Society · 1983
Manaster and Rosenstein [ 1972 ] constructed a recursively bipartite highly recursive graph that satisfies Hall’s condition for a bipartite graph to have a matching, but has no recursive matching. We discuss a natural extension of Hall’s condition which assures that every such graph has a recursive matching.