please provide solution for Q6 Let A and B each be sets of N labeled vertices, and consider bipartite graphs between A and B.1) How many possible ways are there to match or pair vertices between A and B?2) What is the maximum number of edges possible for any bipartite graph between A and B?3) Show by example that there is a bipartite graph between A and B with N² – N edges, and no perfect matching.Questions 2.2 and 2.3 indicate that even if the bipartite graph is almost full of all the edges it might have, it maystill no have a perfect matching. However, we can show that perfect matchings are relatively common with muchless edge-heavy bipartite graphs.4) Starting with no edges between A and B, if N edges are added between A and B uniformly at random, whatis the probability that those N edges form a perfect matching?5) Starting with no edges between A and B, if |E| many edges are addbetween A and B uniformly at random,what is the expected number of perfect matchings in the resulting graph? Hint: if S is a set of edges in apotential perfect matching, let Xs =1 if all the edges in S are added to the graph, and Xs = 0 if any of themare missing. What is E[Xs]? Consider taking |E| = aN, i.e., the total number of edges is proportional to the number of vertices. This is arelatively sparse number of edges, given the total number of edges that can exist between A and B.6) Show that taking |E| = 3N, the expected number of matchings goes to 0 as N → o.7) Show that taking |E| = 4N, the expected number of matchings goes to infinity as N → .We may conclude that constructing random bipartite graphs in this way, perfect matchings become exceedinglycommon once the number of edges crosses some threshold between 3N and 4N, but are relatively uncommon priorto that.The following approximations may be useful in 2.6 and 2.7:(*)1V2TN V a –-1 ( (a – 1)a-11- (eN)NV2T Ne(1)()"N! z V27NBonus: Show that if |E| = 3N, the probability that the generated graph contains even a single perfect matching goesto 0 as N → o.

Question

please provide solution for Q6 Let A and B each be sets of N labeled vertices, and consider bipartite graphs between A and B.1) How many possible ways are there to match or pair vertices between A and B?2) What is the maximum number of edges possible for any bipartite graph between A and B?3) Show by example that there is a bipartite graph between A and B with N² – N edges, and no perfect matching.Questions 2.2 and 2.3 indicate that even if the bipartite graph is almost full of all the edges it might have, it maystill no have a perfect matching. However, we can show that perfect matchings are relatively common with muchless edge-heavy bipartite graphs.4) Starting with no edges between A and B, if N edges are added between A and B uniformly at random, whatis the probability that those N edges form a perfect matching?5) Starting with no edges between A and B, if |E| many edges are addbetween A and B uniformly at random,what is the expected number of perfect matchings in the resulting graph? Hint: if S is a set of edges in apotential perfect matching, let Xs =1 if all the edges in S are added to the graph, and Xs = 0 if any of themare missing. What is E[Xs]? Consider taking |E| = aN, i.e., the total number of edges is proportional to the number of vertices. This is arelatively sparse number of edges, given the total number of edges that can exist between A and B.6) Show that taking |E| = 3N, the expected number of matchings goes to 0 as N → o.7) Show that taking |E| = 4N, the expected number of matchings goes to infinity as N → .We may conclude that constructing random bipartite graphs in this way, perfect matchings become exceedinglycommon once the number of edges crosses some threshold between 3N and 4N, but are relatively uncommon priorto that.The following approximations may be useful in 2.6 and 2.7:(*)1V2TN V a –-1 ( (a – 1)a-11- (eN)NV2T Ne(1)()&#34;N! z V27NBonus: Show that if |E| = 3N, the probability that the generated graph contains even a single perfect matching goesto 0 as N → o.

Accepted Answer

Here, in the question it is given about when the edges are proportional to the vertices. This is a…