MTH 607 - Graph Theory Assignment 4a Due Monday, March 27, 2017 (3pm) For full marks, your answers should be clear, precise and carefully argued. Just having \"the right idea\" will only give you a passing mark. (1) a) Determine the minimum size of a maximal matching in the cycle Cn (n b) Determine the size of a maximum matching in the cycle Cn (n 3). (Note: maximal is not the same as maximum!) 3). (2) a) Determine the minimum size of a maximal matching in the complete graph Kn (n 3). b) Determine the size of a maximum matching in the complete Kn (n 3). (Note: maximal is not the same as maximum!) (3) Do the following two graphs have a perfect matching. If not, find a maximal matching. (4) Prove that a tree T has a perfect matching if and only if o(T \\v) = 1 for every v 2 V (T ). (5) Show that every bipartite, Hamiltonian graph has a perfect matching. Is it also the case for non-bipartite graphs? Show a counterexample if not. (6) Let G = (X [ Y, E) be a bipartite graph such that |N (S)| > |S| whenever ; = 6 S X. Prove that every edge of G belongs to some matching that saturates X. 1