Similar Theorems to Hall's Theorem on Bipartite Graphs

154 Views Asked by At

By Hall's Theorem, a bipartite graph $G$ with vertex sets $V_1$ and $V_2$ contains a complete matching from $V_1$ to $V_2$ if and only if it satisfies Hall's condition

$|\{v\in V_2: uv\in E ~\text{for some $u\in V_1$}\}|\ge |S|$

for every subset $S\subset V_1$. Here $E$ denotes the set of edges of $G$.

Hall's theorem seems to prove useful when working with matchings and graph colorings. Are there any similar theorems on matchings of complete bipartite graphs? I am trying to find any existing results that may potentially prove to be helpful with colorings and matchings.