Question: Let g be a bipartite graph with bipartition sets VI, V2 and assume that g has a perfect matching. Add two vertices x and y to G such that x is adjacent to all vertices in V1, y is adjacent to all vertices in V2, and x is not adjacent to y.
(a) Show that G U {x, y} is bipartite.
(b) Show that GU {x, yl has a perfect matching.