Consider an undirected random graph $G$ of $n$ vertices. The probability that there is an edge between a pair of vertices is $p$.
What is the probability that $G$ is simple cycle of $n$ vertices or tree of $n$ vertices?
My solution:
Number of simple cycles is $\frac{(n - 1)!}{2}$ and number of trees is $n^{n - 2}$.
For every simple cycle prolability is $p^{n - 1}$ $(1 - p)^{(\frac{n}{2}) - n + 1}$ and for every tree probability is $p^{n - 1}$ $(1 - p)^{(\frac{n}{2}) - n + 1}$.
Answer is $(\frac{(n - 1)!}{2} + n^{n - 2}) p^{n - 1} (1 - p)^{(\frac{n}{2}) - n + 1}$.
Is my answer true? Thank you for any help!
Let $T$ be the event that the random graph is a tree, and let $C$ be the event that it is a simple cycle. We are interested in $$P(T\mbox{ or }C) = P(T) + P(C) - P(T\mbox{ and }C) = P(T) + P(C).$$ In a complete graph there are ${n\choose 2}$ edges, and therefore for a fixed graph $G$ with $m$ edges on $n$ vertices, a random graph will be equal to $G$ with probability $$p^m(1-p)^{{n\choose 2}-m}.$$
If $t$ and $c$ are the number of trees and cycles on $n$ vertices, respectively, and $m_t$ and $m_c$ the number of edges in a tree and cycle, respectively, you have $$P(T) = t\cdot p^{m_t}(1-p)^{{n\choose 2}-m_t},\qquad P(C) = c\cdot p^{m_c}(1-p)^{{n\choose 2}-m_c}.$$
I think you can pick it up from here...