Number of Triangles in an Undirected Graph - GeeksforGeeks

Number of Triangles in an Undirected Graph - GeeksforGeeks

Given an Undirected simple graph, We need to find how many triangles it can have. For example below graph have 2 triangles in it.

Let A[][] be adjacency matrix representation of graph. If we calculate A³, then the number of triangle in Undirected Graph is equal to trace(A³) / 6. Where trace(A) is the sum of the elements on the main diagonal of matrix A.

Trace of a graph represented as adjacency matrix A[V][V] is,  trace(A[V][V]) = A[0][0] + A[1][1] + .... + A[V-1][V-1]    Count of triangles = trace(A3) / 6  

Below is C++ implementation of above formula.

Read full article from Number of Triangles in an Undirected Graph - GeeksforGeeks