Number of trees of a specific graph

41 Views Asked by At

I'm here again with another question regarding graphs. In this case, I am asked to find how many possible graphs are there with set of vertices $S = \{1 \dots 2n \}$ such that there are two connected componentes, each one with $n$ vertices, and each connected component has no cycles (that is, it is a tree). My approach seems right for me, although I would be grateful if someone could give me a confirmation:
First I choose $n$ vertices to form the first connected component: $\binom{2n}{n}$. The remaining vertices belong to the other connected component. Now, for each connected component, given $n$ vertices, there are $n^{n-2}$ possible trees that can be formed (Cayley formula). Then, the final result would be $\binom{2n}{n}\cdot (n^{n-2})^2$. Is this right?

1

There are 1 best solutions below

0
On BEST ANSWER

As suggested by @Sammy Black:

No, this is not correct. Luckily you just need to multiply a $1/2$ because you are counting twice the graphs, as it is the same to choose a set $A\subseteq [2n]$ that to choose $A^c$, its complement.