Reference no: EM13928052

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.