Suppose G = (U,V,E) is our bipartite graph and |U| = |V| = n. A matching...

Transcribed Image Text:

Suppose G = (U,V,E) is our bipartite graph and |U| = |V| = n. A matching of size n is called a perfect matching. Of course you know by now how to search for a perfect matching. However, here is a cute algorithm which is faster and works whenever G has a unique perfect matching: M := 0 while G has a vertex u of degree 1 do end let v be the unique neighbor of u add {u, v} to M remove (u, v) from G return M 1. Prove the following statement: If G is a bipartite graph with a unique perfect matching, then G has a vertex of degree 1. 2. Prove that the algorithm is correct, i.e., if G has a unique perfect matching then the algorithm finds it. Suppose G = (U,V,E) is our bipartite graph and |U| = |V| = n. A matching of size n is called a perfect matching. Of course you know by now how to search for a perfect matching. However, here is a cute algorithm which is faster and works whenever G has a unique perfect matching: M := 0 while G has a vertex u of degree 1 do end let v be the unique neighbor of u add {u, v} to M remove (u, v) from G return M 1. Prove the following statement: If G is a bipartite graph with a unique perfect matching, then G has a vertex of degree 1. 2. Prove that the algorithm is correct, i.e., if G has a unique perfect matching then the algorithm finds it.