0
$\begingroup$

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!!

1 Answers 1

2

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$.

  • 0
    aha! I was sort of in the right area, but indeed there was a simpler way to think about it! thanks!!!2012-12-02