In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |NG(W)| < |W|, where NG(W) is the set of neighbors of W in G. If W is a Hall violator, then there is no matching that saturates all vertices of W. Therefore, there is also no matching that saturates X. Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates X.