Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, t...

Question

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

Accepted Answer

Number of 3-cycles = trace(A^3) / 6 The entry (A^k)_{ii} counts the number of closed walks of length k starting and ending at vertex i. For 3-cycles, a walk of length 3 that returns to its start is counted once for each vertex it visits, and in each of two directions, so trace(A^3) over-counts each 3-cycle by a factor of 6 (3 starting vertices × 2 directions).

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