How this question could come in $\mathbf{2019}$. It should be of $\mathbf{2018}$

The Gateway to Computer Science Excellence

+3 votes

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

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

+9 votes

Best answer

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$

**Option B** is answer.

52,218 questions

59,891 answers

201,086 comments

118,129 users