# TIFR2019-B-15

560 views

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

edited
1

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

@srestha

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$

edited
0
I think, answer can be finded by going upto n=3, not need to go for n=4.

Let the first cycle contain k vertices and the second cycle contain n-k vertices. Now we can choose k vertices in nCk ways. The k vertices in the first cycle can be arranged in (k-1)! to give different cycles (here, directed graph is mentioned. So clockwise and anticlockwise ordering will be counted as different and hence, no need to divide it by 2). Similarly, the remaining n-k vertices in the second cycle can be arranged in (n-k-1)! ways to give different cycles. Thus, the total number of cycles, will be given as

f(k)   = $\binom{n}{k}.(n-1)!.(n-k-1)!$

= $\tfrac{n!}{(k.(k-1)! . (n-k).(n-k-1)!)} . (k-1)! . (n-k-1)!$

= $\tfrac{n!}{k(n-k)}$

The value of k can range from 1 to n-1, and summing up all the cases will give us the total number of graphs that will have exactly two cycles. However, here we are distinguishing between first and second cycles. So we will need to divide by 2 because each graph will be counted twice. (Consider two graphs G1 and G2 such that first cycle of G1 is same as second cycle of G2 and vice versa. We have counted these graphs twice but essentially they are the same and so we need to divide the total number by 2). Therefore, the total number of graphs will be:-

$T =\tfrac{1}{2} \sum_{k=1}^{n-1} \tfrac{n!}{k(n-k)} = \tfrac{n!}{2} \sum_{k=1}^{n-1} \tfrac{1}{k(n-k)}$

## Related questions

1
395 views
A graph is $d$ – regular if every vertex has degree $d$. For a $d$ – regular graph on $n$ vertices, which of the following must be TRUE? $d$ divides $n$ Both $d$ and $n$ are even Both $d$ and $n$ are odd At least one of $d$ and $n$ is odd At least one of $d$ and $n$ is even
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ ... $H^*$ is acyclic $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
Consider the matrix $A = \begin{bmatrix} \frac{1}{2} &\frac{1}{2} & 0\\ 0& \frac{3}{4} & \frac{1}{4}\\ 0& \frac{1}{4} & \frac{3}{4} \end{bmatrix}$ What is $\lim_{n→\infty}$A^n$?$\begin{bmatrix} \ 0 & 0 & 0\\ 0& 0 & 0\\ 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} ... $\text{The limit exists, but it is none of the above}$
McCabe&rsquo;s cyclomatic metric $V(G)$ of a graph $G$ with $n$ vertices, $e$ edges and $p$ connected component is $e$ $n$ $e &ndash; n + p$ $e &ndash; n + 2p$