0 votes 0 votes 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 Mathematical Logic graph-matching graph-theory discrete-mathematics + – Na462 asked Oct 13, 2018 Na462 1.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Na462 commented Oct 13, 2018 reply Follow Share What is complete matching is it Perfect matching. Please explain the terms as well :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes 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 Utkarsh Joshi answered Oct 13, 2018 selected Oct 18, 2018 by Na462 Utkarsh Joshi comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments mohan123 commented Sep 9, 2019 reply Follow Share @Bikram 0 votes 0 votes Bikram commented Sep 10, 2019 reply Follow Share https://courses.cit.cornell.edu/info204_2007sp/matching.pdf https://gateoverflow.in/926/gate2003-36 1 votes 1 votes Bikram commented Sep 10, 2019 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.