+1 vote
276 views

Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ?

1. $\sum_{k=1}^{n-1} k!(n-k)!$
2. $\frac{n!}{2}\bigg[\sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$
3. $n!\bigg[\sum_{k=1}^{n-1} \frac{1}{k}\bigg]$
4. $\frac{n!(n-1)}{2}$
5. None of the above

edited | 276 views

We need to find from $\{1,2,\ldots,n\}$ vertices how many graphs exist which are having exactly two cycles when self loops are allowed.

When $n=1$ there is no such graph with two cycles.

0 graph.

When $n=2$

1 graph exists.

When $n=3$

3 graphs exist.

When $n=4$

11 graphs exist.

For $n=4$

(A) $\sum_{k=1}^{n-1}k!(n-k)! = 16$

(B) $\frac{n!}{2}[\sum_{k=1}^{n-1}\frac{1}{k(n-k)}] = 11$

(C) $n![\sum_{k=1}^{n-1}\frac{1}{k}] = 44$

(D) $\frac{n!(n-1)}{2} = 36$

by Loyal (9k points)
edited

1
+1 vote
2