Let's go to a similar problem, similar in terms of what we get eventually. Matching. We are given a graph and a matching is this set of arcs with at most one arc for each node. Clearly we have to have these degree constraints for each node; not more than one arc has to be incident in each node.