A bipartite graph, G = (V, E), is a graph such that V can be partitioned into two subsets,...

A bipartite graph, G = (V, E), is a graph such that V can be partitioned into two subsets, V1 and V2, and no edge has both its vertices in the same subset.

a. Give a linear algorithm to determine whether a graph is bipartite.

---

b. The bipartite matching problem is to find the largest subset E′ of E such that no vertex is included in more than one edge. A matching of four edges (indicated by dashed edges) is shown in Figure 1. There is a matching of five edges, which is maximum.

Show how the bipartite matching problem can be used to solve the following problem:

We have a set of instructors, a set of courses, and a list of courses that each instructor is qualified to teach. If no instructor is required to teach more than one course, and only one instructor may teach a given course, what is the maximum number of courses that can be offered?

---

c. Show that the network flow problem can be used to solve the bipartite matching problem.

---

d. What is the time complexity of your solution to part (b)?

Figure 1: A bipartite graph