GATE 2022 CS Q.37: solution and answer

GATE 2022 · CSQ.37 · 2 marks · MCQ

Consider a simple undirected unweighted graph with at least three vertices. If $A$ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

(A)
$A^{3}$
(B)
$A^{3}$ divided by 2
(C)
$A^{3}$ divided by 3
(D)
$A^{3}$ divided by 6

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of 3-cycles equals $tr (A^{3}) /6$ , so the answer is option (D).

Official answer: DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

The entry $(A^{k})_{ii}$ counts the closed walks of length $k$ that start and end at vertex $i$ , because $(A^{k})_{ij}$ counts walks of length $k$ from $i$ to $j$ .
So $tr (A^{3}) = \sum_{i} (A^{3})_{ii}$ is the total number of closed walks of length 3, summed over all starting vertices.
In a simple graph there are no loops and no multi-edges. A closed walk $i \to j \to k \to i$ then needs $i \neq = j$ , $j \neq = k$ and $k \neq = i$ . So it is a triangle on three distinct vertices.
Each triangle gives $3$ choices of starting vertex and $2$ directions of travel. That is $3 \times 2 = 6$ closed walks.
Hence $tr (A^{3}) = 6 \times (number of triangles)$ .
Check on $K_{3}$ : $A = J - I$ has eigenvalues $2, - 1, - 1$ . So $tr (A^{3}) = 8 - 1 - 1 = 6$ , which is $1$ triangle times $6$ .
The number of 3-cycles is $tr (A^{3}) /6$ , which is option (D).

KEY IDEA

$tr (A^{3})$ counts closed walks of length 3. In a simple graph each triangle contributes exactly $3 \times 2 = 6$ of them, so divide the trace by 6.

WATCH OUT FOR

Dividing by 3 and forgetting the two directions of travel. Dividing by 2 and forgetting the three choices of starting vertex. Both give the wrong count.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2022 CS Q.37: solution and answer

Answer and solution

More Graph theory questions