Complete Matching

Question

Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ?

A. 0.039

B. 0.052

C. 0.071

D. 0.083

Comments

What is complete matching is it Perfect matching. Please explain the terms as well :)

Answer 1

5 complete matchings are possible!

for C we have to fix T otherwise we won't get a complete matching.

For( A,B,D) following 5 matchings are possible: (P,S,Q) (P,S,R) (Q P,R) (Q,P,S) (Q,S,R).

Hence P= 5/ 8C4= 5/70=0.071

Comments

Is Complete Matching , other name of perfect matching?

---

In this graph their are odd number of vertices, how can we have complete matching in this in Question when we can not select all the vertices.

---

@Bikram 

---

https://courses.cit.cornell.edu/info204_2007sp/matching.pdf

 

https://gateoverflow.in/926/gate2003-36

---

https://mathoverflow.net/questions/279690/graph-to-bipartite-conversion-preserving-number-of-perfect-matchings

 

https://www.whitman.edu/mathematics/cgt_online/book/section04.05.html