Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$.

What is the number of random graphs that has a perfect matching?

I think that the number of possible graphs is $2^{n^2}$, but I can't find how many of them has a perfect match.

share|improve this question
You might look at: math.cmu.edu/~af1p/Texfiles/matchplusbip.pdf –  Joseph Malkevitch Oct 27 '12 at 18:46
What is your random model? Each of the $n^2$ edges is independently chosen to be either present or not, with probability $p = 1/2$? –  ShreevatsaR Oct 27 '12 at 18:58
Each of the n^2 edges is independently chosen to be present with probability p=n/3. but the probability doesn't affect the number of graphs. –  user844541 Oct 27 '12 at 19:08
You talk about random graphs but really you just mean "What is the number of graphs..." not "random graphs", right? If you want to count the number of "random graphs" that has some property, aren't you just counting the number of "graphs" that has the property? And, if so, then there's no reason to mention anything about random. You might use random graphs to prove something, but the statement has nothing to do with random graphs. Am I misunderstanding something? –  Graphth Oct 27 '12 at 19:28
you are rignt. I am actually trying to find the probability, but I want to do that as much as I can on my own. –  user844541 Oct 27 '12 at 19:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.