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 ?

  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
in Graph Theory by Veteran
edited by | 462 views

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


1 Answer

+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.

by Loyal
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,891 answers
118,129 users