I have the following question in my homework and I'm not sure how to go about proving it. Hall's Theorem states that the graph contains a matching saturating X is and only if |N(S)| >= |S| for all S _( X. First of all in this question it says that the first part is only greater and the second part is strictly a subset. Am I correct in interpreting the following: Since S is a non-empty subset of X, and N(S) > S for all S, doesn't that mean that every vertex in X has at least 2 edges going to Y? Because I could make S any single vertex and then I would have N(S) > S so there must be more than one edge going from X to Y right? If this is true, how does this help me make my proof?
Best Answer
Your interpretation is correct, but I'm not sure if it is useful.
Take your graph and pick some edge $e \in E$. Then remove $e$ along with the two vertices it connects. Look for a matching in this new graph. Do you see a connection between a matching in this new graph and a matching in the original graph? Can you conclude that $e$ belongs to some matching of the original graph?