1. For each of the following graphs find a 1-factor or explain why one cannot exist (via Tuttes). ie Find a set S such that |S| < |o(G-S)|.

   (a)		(b)		(c)
   (d)		(e)		(f)

2. Use Tuttes Theorem to show that K_3,5 does not have a 1-factor.

3. Find a 1-factorization of the graphs below

   1. 

   2. 

4. Show that K_n,n has a 1-factorization for any n.

5. Show that no tree with at least three vertices has a 1-factorization.

Peter Danziger, March 2008