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).