Before revision: A bipartite graph consists of two disjoint vertex sets, where vertices of one set can only be joined with an edge to vertices in the opposite set. Hall's theorem gives a necessary and sufficient condition for a bipartite graph to have a saturating matching , meaning every vertex in one set is matchedto some vertex in the other in a one-to-one correspondence.
After revision: I relate bipartite graph matchings to stable matchings. I prove a necessary and sufficient condition for a bipartite graph to have a saturating matching , meaning every vertex in one set is matchedto some vertex in the other in a one-to-one correspondence.