Log In
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
edited by

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


2 Answers

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

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

Answer : Option B

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

2 votes
1 answer
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
asked Dec 18, 2018 in Graph Theory Arjun 395 views
3 votes
1 answer
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
asked Dec 18, 2018 in Graph Theory Arjun 591 views
4 votes
5 answers
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}$
asked Dec 18, 2018 in Calculus Arjun 655 views
2 votes
2 answers
McCabe’s cyclomatic metric $V(G)$ of a graph $G$ with $n$ vertices, $e$ edges and $p$ connected component is $e$ $n$ $e – n + p$ $e – n + 2p$
asked Aug 14, 2016 in Graph Theory makhdoom ghaya 439 views