CSDS 455: Applied Graph Theory
Homework 3
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).
