[Solved] CSDS455 Homework3

Problem 1: Let G be a bipartite graph, let A and B be the partition sets of V (G), and suppose we have the following fact: for every S A, |S| |N(S)|. (N(S) is the set of vertices of B adjacent to a vertex of S.) Let M be a matching of G and let a A be an unmatched vertex. Prove that there exists an augmenting path in G with respect to M starting from a.

Problem 2: Let G be a bipartite graph, and let A and B be partition sets of V (G). Given S A, define the deficiency of S to be |S| |N(S)|. (The deficiency of is 0.) Let Def(A) be the maximum deficiency of over all sets S A. Prove that the size of the maximum matching of G is equal to |A| Def(A).

Problem 3: Let q(H) be the number of components of (not necessarily connected) graph H that contain an odd number of vertices. Prove that a tree T has a perfect matching if and only if q(T v) = 1 for all v V (T).