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.

The problem is as follows. Given a set $V$ of $n$ vertices, and an empty set of edges $E$, for every possible edge $(u,v)$ in the graph, choose to include add it to $E$ with probability $1/2$. What is the probability that the final product is a tree?

I'm going in circles on this one, having no idea where to start. Here's my thinking so far: I know we'll need to choose exactly $(n-1)$ edges, and there are a total of $\binom{n}{2}$ possible edges. This means you need to choose to include an edge $(n-1)$ times out of $\binom{n}{2}$ times, and since there are a total of $2^\binom{n}{2}$ possible sequences of choices, the probability of choosing exactly $n-1$ edges is $$\binom{\binom{n}{2}}{n-1} / 2^{\binom{n}{2}}.$$ However, not all of these will be trees. By Cayley's theorem there are $n^{n-2}$ total trees on $n$ vertices, but I don't know how to calculate how many general graphs (i.e. including disconnected graphs) there are with $n$ vertices and $n-1$ edges. So I'm not sure how to formulate this. And perhaps I'm overlooking a much simpler way to calculate these. Help!!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Each tree has probability $1/2^e$ to be realized, where $e={n\choose 2}$. There are $n^{n-2}$ trees hence the probability to realize a tree is $n^{n-2}/2^e$.

share|improve this answer
    
aha! I was sort of in the right area, but indeed there was a simpler way to think about it! thanks!!! –  limp_chimp Dec 2 '12 at 22:38

Your Answer

 
discard

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.