6. (12 points total) Let G=(V,E) be a bipartite graph with a given bipartition (X,Y) (i.e., XY=V,XY=, and every edge in E has one endpoint in X and one endpoint in Y ). Let G=(V,E) denote the flow network derived from G=(V,E) as follows. First, we define V as V{s,t}. Second, we define the set of directed edges E as E1E2E3 where E1 includes a directed edge from s to x for each x in X,E2 includes a directed edge from x to y for each x in X and y in Y such that (x,y) belongs to E, and E3 includes a directed edge from y to t for each y in Y. Third, we assign unit capacity to each edge in E. (a) (4 points) Prove that if there is a matching of cardinality k in G, then there is an integer flow of value k in G. (b) (3 points) Explain why there is an integer maximum flow in G. (c) (5 points) Prove that if the value of a maximum flow in G is k, then there is a matching of cardinality k in G