In a bipartite graph, how can we find the total number of ways of getting a maximal matching?

The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to be different if they have at least one distinct edge.

  • $\begingroup$ @Raphael - I think this question should be unmarked as duplicate. The question you've referred to has been recently put on hold as unclear, and it looks like its frustrated author has closed his/her account. Additionally, a similar question has been asked on SO recently, and I have given my answer, but this question has been put on hold as well. It looks like a war against the question! But actually it's a valid combinatorial question in case of complete bigraphs, and also a valid algorithmic question in case of general bigraphs. $\endgroup$
    – HEKTO
    Aug 3, 2014 at 17:19
  • $\begingroup$ @HEKTO I think this here question would be closed as unclear for the same reasons as the duplicate. The OP can improve their question at any time. $\endgroup$
    – Raphael
    Aug 3, 2014 at 17:23
  • $\begingroup$ @Raphael - The question is formulated in such a way that it's evident the terminology is new to its author - but CS professionals can extract its real meaning, do they? $\endgroup$
    – HEKTO
    Aug 3, 2014 at 17:31
  • 1
    $\begingroup$ Your question may or may not be the same as that earlier one… Both questions are unclear. They're clearly about the same topic — the number of maximal matchings in a bipartite graph — but what is your question on this topic? Have you read Wikipedia? $\endgroup$ Aug 3, 2014 at 23:15
  • 1
    $\begingroup$ What research have you done? Where have you looked? What have you found so far on this topic? On this site, we expect you to make a significant effort on your own before asking, and to tell us in the question what you've tried. (Cc: @HEKTO.) $\endgroup$
    – D.W.
    Aug 14, 2014 at 20:48


Browse other questions tagged or ask your own question.