The following is a statement of Hall's1•1 theorem. If G = (V, E) is a bipartite graph with bipartition (V', V"'), then G has a complete matching of V' onto V" if and only if: jN(Vi)I...

1. 
   

   
   The following is a statement of Hall's1•1 theorem. If G = (V, E) is a
   

   
   

bipartite graph with bipartition (V', V"'), then G has a complete matching of V' onto V" if and only if:

jN(Vi)I ;;i, Iv:1. for all v: s; V'

where N(VD is the set of vertices adjacent to v:.

Obtain Hall's theorem from theorem 5.2.

(Suppose that IVI is even. We can construct G* by adding to G an edge joining every pair of vertices in V... Show that G has a matching, with

every vertex of V' an end-point of an element of the matching, if and only if G* has a perfect matching. Hall's theorem then follows naturally. For IVI odd, a simple modification to the proof is required.)