Matching saturation
= Matching saturation
A <matching in a graph> saturates a specified <vertex set> $X$ when every <vertex> of $X$ is incident to one selected <edge>. Exactly one selected <edge> meets each such <vertex>, since matching <edges> have disjoint endpoints. <Vertices> outside $X$ may remain unmatched. A <perfect matching> saturates the entire <vertex set>; <Hall's marriage theorem> tests <matching saturation> of a specified side in a finite <bipartite graph>.