# Predicting the number of simple circuits in a graph

If I have a directed graph with $n$ vertices, and the mean number of out-edges per vertex is $x$, what is the expected number of simple circuits that will be found in the graph?

What happens to the result if we introduce the constraint that each edge can belong to only one circuit?

• What, precisely, is the random process by which the edges are drawn? You've specified that the mean number of out-edges per vertex is $x$. Does that mean we just draw $nx$ edges at random in the graph? – 6005 Apr 21 '14 at 13:04
• Apologies for leaving out that relevant information. I don't actually know how my real-life graph will look, or what the distribution of edges will be. Is it sufficient for me to say to simply assume a nearly uniform distribution? – Sully Apr 22 '14 at 5:07

There are, on average, $\binom{n-1}{x}$ ways to choose an outgoing neighborhood of $v_{1}$. The vertex $v_{2}$ will be $\binom{n-2}{x-1}$ of these neighborhoods. So simply divide out: $$P( (v_{1}, v_{2}) \in E(G) ) = \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$$
Now for a two-cycle, we want an outgoing arc from $v_{2}$ to $v_{1}$. The probability is the same as we found above, so we multiply. There are $\binom{n}{2} p(C_{2})^{2}$ such cycles we would expect.
For three cycles, we start with by going from $v_{1} \to v_{2}$, with probability $\dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$. We then pick $v_{3}$, and it has the same probability of being in $v_{2}$'s neighborhood.
So now we want the probability of $v_{3}$ having $v_{1}$ in its neighborhood, which is again the same probability as above. So $E(C_{3}) = \binom{n}{3} (\dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} })^{3}$.