Deficiency (graph theory)

The deficiency of the set of red vertices U is the size of U minus the size of the set of all vertices that are neighbors of a vertex in U (the blue vertices)

Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by Øystein Ore. A related property is surplus.