Defect Hall's Theorem

Let Graph be bipartite. Then contains a Matching with Deficiency if and only if

for all

Proof

Forward direction is easy Now apply Hall’s Theorem on graph:

where

After finding the Matching, remove the vertices Because of injectivity, we get a Matching with Deficiency at most Then remove a few edges to get deficiency