1. For each of the graphs below:
   1. Find a maximum matching.
   2. If possible find a matching which is maximal but not not maximum.
   3. If G is bipartite, with parts X, Y,
      1. List X and Y.
      2. Either find an X saturating matching or find a set S such that |S| > |N(S)|.
      3. Do the same for Y.

      

      1. (a, c), (b, d) or (a, b), (c, d).
      2. All maximal matchings are maximum.
      3. 1. X = {a, d}, Y = {b, c}
         2. Either of the matchings above
         3. Either of the matchings above

      

      1. (r, a) (b, e)
      2. All maximal matchings are maximum.
      3. 1. X = {a, b}, Y = {r, c, d, e}
         2. (r, a), (b, e) is X saturating
         3. |{c, d}| = 2, but |N({c, d})| = |{a}| = 1.

      

      1. (b, e), (a, r), (c, d)
      2. (b, r), (a, c)
      3. 1. X = {r, c, e}, Y = {a, b, d}
         2. The answer to part a. is X saturating
         3. The answer to part a. is Y saturating

2. For each of the following graphs find
   1. α(G)
   2. α'(G)
   3. β(G)
   4. β'(G)
   5. Either find a 1-factor or explain why one cannot exist (via Tuttes).
   1. 
      1. α(G) = 4, {r, c, d, e} is an independent set.
      2. α'(G) = 2.
      3. β(G) = 2 {a, b} is a vertex cover.
      4. β'(G) = 4 {ac, ad, be, ra} is an edge cover.
      5. Either find a 1-factor or explain why one cannot exist (via Tuttes).
         G - a has three odd components so |{a}| = 1 < o(G-a)=3 and thus no one factor can exist.

   2. 
      1. α(G) = 3.
      2. α'(G) = 4
      3. β(G) = 6.
      4. β'(G) = 5.
      5. Either find a 1-factor or explain why one cannot exist (via Tuttes).
         G has an odd number of vertices and so cannot have a 1-factor. Via Tuttes, S = Φ, 0 = |S| < o(G - S) = 1.

   3. 
      1. α(G) = 3, {r, c, e} is an independent set.
      2. α'(G) = 2.
      3. β(G) = 3, {a, b, d} is a vertex cover.
      4. β'(G) = 4 {ac, ad, be, ra} is an edge cover.
      5. ca, rb, de is a 1-factor.

   4. 
      1. α(G) = 2
      2. α'(G) = 3.
      3. β(G) = 3.
      4. β'(G) = 3.

   5. 
      1. α(G) = 3, {000, 110, 011} is an independent set.
      2. α'(G) = 4, { {000, 100}, {001, 101}, {111, 011}, {110, 010} } is a perfect matching.
      3. β(G) = 4, { 000, 110, 101, 011 } is a vertex cover.
      4. β'(G) = 4. The perfect matching in ii is also a vertex cover.
      5. The perfect matching in ii is also a 1-factor.

3. In each case give the general class of simple connected graphs G that satisfy the given property:
   1. α(G) = 1

      K_n

   2. α'(G) = 1

      K_1,n - an n star.

   3. β(G) = 1

      K_1,n - an n star.

   4. β'(G) = 1

      K₂.

4. 1. Show that for any graph G β(G) ≤ 2 α'(G).

      Let G be a graph and let B be a minimum vertex cover.
      So |B| = β(G).
      Since B is incident on every edge any matching must have each edge incident on some vertex of B.
      

   2. Find graphs for each k so that α'(G) = k and β(G) = 2k.

      A collection of triangles.

Peter Danziger, March 2008