Hall's Theorem(graph theory form) A bipartite graph G(U,V,E)has a matching of U → lW(S)l≥ISl for all SCU matching:edge independent set MCE with no e1,e2CM share a vertex W(S)={vI3u∈S,uv∈E} VHall’s Theorem (graph theory form) A bipartite graph G(U,V,E) has a matching of U |N(S)| ≥ |S| for all S⊆U U V matching: edge independent set M⊆E with no e1,e2∈M share a vertex N(S) = {v | ∃u∈S, uv∈E}