Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
You might look at: – 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

In all perfect matching, each $U$ must be joined to a $V$ and vice versa.

There are $n$ possible $U$. Start with $u_1$ - it can be joined to any $V$ and therefore there are $n$ possible choices.

Next is $u_2$. Because $u_1$ took up one $V$, it can be joined in $n-1$ possible ways.

Continuing this, we get $n.(n-1).(n-2)...1=n!$ different perfect matchings possible.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.