A. Show that a graph G contains k independent edges if and only if q(G - S) ≤ |S| + |G| - 2k for all sets S ⊆ V (G).
Hint : For the 'if' direction apply Tutte's 1-factor theorem to the graph G ∗ K|G|-2k, or use the remarks on maximum-cardinality matchings following Theorem 2.2.3.
B. Find a cubic graph without a 1-factorHint : Corollary 2.2.2.
C. Derive the marriage theorem from Tutte's theorem
Hint : Let G be a bipartite graph that satisfies the marriage condition, with bipartition { A,B } say. Reduce the problem to the case of |A| = |B|. To verify the premise of Tutte's theorem for a given set S ⊆ V (G), bound |S| from below in terms of the number of components of G - S that contain more vertices from A than from B and vice versa.