# Number of Triangles in an Undirected Graph

• Difficulty Level : Hard
• Last Updated : 01 Sep, 2022

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 the adjacency matrix representation of the graph. If we calculate A3, then the number of triangles in Undirected Graph is equal to trace(A3) / 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 + A + .... + A[V-1][V-1]

Count of triangles = trace(A3) / 6```

Below is the implementation of the above formula.

## C++

 `// A C++ program for finding``// number of triangles in an``// Undirected Graph. The program``// is for adjacency matrix``// representation of the graph``#include ``using` `namespace` `std;` `// Number of vertices in the graph``#define V 4` `//  Utility function for matrix``// multiplication``void` `multiply(``int` `A[][V], ``int` `B[][V], ``int` `C[][V])``{``    ``for` `(``int` `i = 0; i < V; i++)``    ``{``        ``for` `(``int` `j = 0; j < V; j++)``        ``{``            ``C[i][j] = 0;``            ``for` `(``int` `k = 0; k < V; k++)``                ``C[i][j] += A[i][k]*B[k][j];``        ``}``    ``}``}` `// Utility function to calculate``// trace of a matrix (sum of``// diagonal elements)``int` `getTrace(``int` `graph[][V])``{``    ``int` `trace = 0;``    ``for` `(``int` `i = 0; i < V; i++)``        ``trace += graph[i][i];``    ``return` `trace;``}` `//  Utility function for calculating``// number of triangles in graph``int` `triangleInGraph(``int` `graph[][V])``{``    ``// To Store graph^2``    ``int` `aux2[V][V];` `    ``// To Store graph^3``    ``int` `aux3[V][V];` `    ``//  Initialising aux``    ``// matrices with 0``    ``for` `(``int` `i = 0; i < V; ++i)``        ``for` `(``int` `j = 0; j < V; ++j)``            ``aux2[i][j] = aux3[i][j] = 0;` `    ``// aux2 is graph^2 now  printMatrix(aux2);``    ``multiply(graph, graph, aux2);` `    ``// after this multiplication aux3 is``    ``// graph^3 printMatrix(aux3);``    ``multiply(graph, aux2, aux3);` `    ``int` `trace = getTrace(aux3);``    ``return` `trace / 6;``}` `// driver code``int` `main()``{` `    ``int` `graph[V][V] = {{0, 1, 1, 0},``                       ``{1, 0, 1, 1},``                       ``{1, 1, 0, 1},``                       ``{0, 1, 1, 0}``                      ``};` `    ``printf``(``"Total number of Triangle in Graph : %d\n"``,``            ``triangleInGraph(graph));``    ``return` `0;``}`

## Java

 `// Java program to find number``// of triangles in an Undirected``// Graph. The program is for``// adjacency matrix representation``// of the graph``import` `java.io.*;` `class` `Directed``{``    ``// Number of vertices in``    ``// the graph``    ``int` `V = ``4``;`` ` `   ``//  Utility function for``   ``// matrix multiplication``   ``void` `multiply(``int` `A[][], ``int` `B[][],``                            ``int` `C[][])``   ``{``       ``for` `(``int` `i = ``0``; i < V; i++)``       ``{``           ``for` `(``int` `j = ``0``; j < V; j++)``           ``{``               ``C[i][j] = ``0``;``               ``for` `(``int` `k = ``0``; k < V;``                                   ``k++)``               ``{``                   ``C[i][j] += A[i][k]*``                              ``B[k][j];``               ``}``           ``}``       ``}``   ``}`` ` `   ``// Utility function to calculate``   ``// trace of a matrix (sum of``   ``// diagonal elements)``   ``int` `getTrace(``int` `graph[][])``   ``{``       ``int` `trace = ``0``;` `       ``for` `(``int` `i = ``0``; i < V; i++)``       ``{``           ``trace += graph[i][i];``       ``}``       ``return` `trace;``   ``}`` ` `   ``// Utility function for``   ``// calculating number of``   ``// triangles in graph``   ``int` `triangleInGraph(``int` `graph[][])``   ``{``       ``// To Store graph^2``       ``int``[][] aux2 = ``new` `int``[V][V]; ` `       ``// To Store graph^3``       ``int``[][] aux3 = ``new` `int``[V][V];`` ` `       ``// Initialising aux matrices``       ``// with 0``       ``for` `(``int` `i = ``0``; i < V; ++i)``       ``{``           ``for` `(``int` `j = ``0``; j < V; ++j)``           ``{``               ``aux2[i][j] = aux3[i][j] = ``0``;``           ``}``       ``}`` ` `       ``// aux2 is graph^2 now``       ``// printMatrix(aux2)``       ``multiply(graph, graph, aux2);`` ` `       ``// after this multiplication aux3``       ``// is graph^3 printMatrix(aux3)``       ``multiply(graph, aux2, aux3);`` ` `       ``int` `trace = getTrace(aux3);` `       ``return` `trace / ``6``;``   ``}`` ` `   ``// Driver code``   ``public` `static` `void` `main(String args[])``   ``{``       ``Directed obj = ``new` `Directed();``       ` `       ``int` `graph[][] = { {``0``, ``1``, ``1``, ``0``},``                         ``{``1``, ``0``, ``1``, ``1``},``                         ``{``1``, ``1``, ``0``, ``1``},``                         ``{``0``, ``1``, ``1``, ``0``}``                       ``};` `       ``System.out.println(``"Total number of Triangle in Graph : "``+``              ``obj.triangleInGraph(graph));``   ``}``}` `// This code is contributed by Anshika Goyal.`

## Python3

 `# A Python3 program for finding number of``# triangles in an Undirected Graph. The``# program is for adjacency matrix``# representation of the graph` `# Utility function for matrix``# multiplication``def` `multiply(A, B, C):``    ``global` `V``    ``for` `i ``in` `range``(V):``        ``for` `j ``in` `range``(V):``            ``C[i][j] ``=` `0``            ``for` `k ``in` `range``(V):``                ``C[i][j] ``+``=` `A[i][k] ``*` `B[k][j]` `# Utility function to calculate``# trace of a matrix (sum of``# diagonal elements)``def` `getTrace(graph):``    ``global` `V``    ``trace ``=` `0``    ``for` `i ``in` `range``(V):``        ``trace ``+``=` `graph[i][i]``    ``return` `trace` `# Utility function for calculating``# number of triangles in graph``def` `triangleInGraph(graph):``    ``global` `V``    ` `    ``# To Store graph^2``    ``aux2 ``=` `[[``None``] ``*` `V ``for` `i ``in` `range``(V)]` `    ``# To Store graph^3``    ``aux3 ``=` `[[``None``] ``*` `V ``for` `i ``in` `range``(V)]` `    ``# Initialising aux``    ``# matrices with 0``    ``for` `i ``in` `range``(V):``        ``for` `j ``in` `range``(V):``            ``aux2[i][j] ``=` `aux3[i][j] ``=` `0` `    ``# aux2 is graph^2 now printMatrix(aux2)``    ``multiply(graph, graph, aux2)` `    ``# after this multiplication aux3 is``    ``# graph^3 printMatrix(aux3)``    ``multiply(graph, aux2, aux3)` `    ``trace ``=` `getTrace(aux3)``    ``return` `trace ``/``/` `6` `# Driver Code` `# Number of vertices in the graph``V ``=` `4``graph ``=` `[[``0``, ``1``, ``1``, ``0``],``         ``[``1``, ``0``, ``1``, ``1``],``         ``[``1``, ``1``, ``0``, ``1``],``         ``[``0``, ``1``, ``1``, ``0``]]` `print``(``"Total number of Triangle in Graph :"``,``                    ``triangleInGraph(graph))` `# This code is contributed by PranchalK`

## C#

 `// C# program to find number``// of triangles in an Undirected``// Graph. The program is for``// adjacency matrix representation``// of the graph``using` `System;` `class` `GFG``{``// Number of vertices``// in the graph``int` `V = 4;` `// Utility function for``// matrix multiplication``void` `multiply(``int` `[,]A, ``int` `[,]B,``                        ``int` `[,]C)``{``    ``for` `(``int` `i = 0; i < V; i++)``    ``{``        ``for` `(``int` `j = 0; j < V; j++)``        ``{``            ``C[i, j] = 0;``            ``for` `(``int` `k = 0; k < V;``                              ``k++)``            ``{``                ``C[i, j] += A[i, k]*``                           ``B[k, j];``            ``}``        ``}``    ``}``}` `// Utility function to``// calculate trace of``// a matrix (sum of``// diagonal elements)``int` `getTrace(``int` `[,]graph)``{``    ``int` `trace = 0;` `    ``for` `(``int` `i = 0; i < V; i++)``    ``{``        ``trace += graph[i, i];``    ``}``    ``return` `trace;``}` `// Utility function for``// calculating number of``// triangles in graph``int` `triangleInGraph(``int` `[,]graph)``{``    ``// To Store graph^2``    ``int``[,] aux2 = ``new` `int``[V, V];` `    ``// To Store graph^3``    ``int``[,] aux3 = ``new` `int``[V, V];` `    ``// Initialising aux matrices``    ``// with 0``    ``for` `(``int` `i = 0; i < V; ++i)``    ``{``        ``for` `(``int` `j = 0; j < V; ++j)``        ``{``            ``aux2[i, j] = aux3[i, j] = 0;``        ``}``    ``}` `    ``// aux2 is graph^2 now``    ``// printMatrix(aux2)``    ``multiply(graph, graph, aux2);` `    ``// after this multiplication aux3``    ``// is graph^3 printMatrix(aux3)``    ``multiply(graph, aux2, aux3);` `    ``int` `trace = getTrace(aux3);` `    ``return` `trace / 6;``}` `// Driver code``public` `static` `void` `Main()``{``    ``GFG obj = ``new` `GFG();``        ` `    ``int` `[,]graph = {{0, 1, 1, 0},``                    ``{1, 0, 1, 1},``                    ``{1, 1, 0, 1},``                    ``{0, 1, 1, 0}};` `    ``Console.WriteLine(``"Total number of "` `+``                   ``"Triangle in Graph : "``+``              ``obj.triangleInGraph(graph));``}``}` `// This code is contributed by anuj_67.`

## Javascript

 ``

Output:

`Total number of Triangle in Graph : 2`

How does this work?
If we compute An for an adjacency matrix representation of the graph, then a value An[i][j] represents the number of distinct walks between vertex i to j in the graph. In A3, we get all distinct paths of length 3 between every pair of vertices.
A triangle is a cyclic path of length three, i.e. begins and ends at the same vertex. So A3[i][i] represents a triangle beginning and ending with vertex i. Since a triangle has three vertices and it is counted for every vertex, we need to divide the result by 3. Furthermore, since the graph is undirected, every triangle twice as i-p-q-j and i-q-p-j, so we divide by 2 also. Therefore, the number of triangles is trace(A3) / 6.

```Time Complexity: O(V3) (as here most time consuming part is multiplication of matrix which contains 3 nested for loops)
Space Complexity: O(V2) (to store matrix of size V*V)```

Time Complexity:
The time complexity of above algorithm is O(V3) where V is number of vertices in the graph, we can improve the performance to O(V2.8074) using Strassen’s matrix multiplication algorithm.

Another approach: Using Bitsets as adjacency lists.

• For each node in the graph compute the corresponding adjacency list as a bitmask.
• If two nodes, i & j, are adjacent compute the number of nodes that are adjacent to i & j and add it to the answer.
• In the end, divide the answer by 6 to avoid duplicates.

In order to compute the number of nodes adjacent to two nodes, i & j, we use the bitwise operation & (and) on the adjacency list of i and j, then we count the number of ones.

Below is the implementation of the above approach:

## C++

 `#include``#include``#include``#include``#include``#include` `using` `namespace` `std;` `#define V 4` `int` `main()``{``    ``// Graph represented as adjacency matrix``    ``int` `graph[][V] = {{0, 1, 1, 0},``                      ``{1, 0, 1, 1},``                      ``{1, 1, 0, 1},``                      ``{0, 1, 1, 0}};` `    ``// create the adjacency list of the graph (as bit masks)``    ``// set the bits at positions [i][j] & [j][i] to 1, if there is an undirected edge between i and j``    ``vector> Bitset_Adj_List(V);``    ``for` `(``int` `i = 0; i < V;i++)``        ``for` `(``int` `j = 0; j < V;j++)``            ``if``(graph[i][j])``                ``Bitset_Adj_List[i][j] = 1,``                ``Bitset_Adj_List[j][i] = 1;` `    ``int` `ans = 0;` `    ``for` `(``int` `i = 0; i < V;i++)``        ``for` `(``int` `j = 0; j < V;j++)``            ` `            ``// if i & j are adjacent``            ``// compute the number of nodes that are adjacent to i & j``            ``if``(Bitset_Adj_List[i][j] == 1 && i != j){``                ``bitset Mask = Bitset_Adj_List[i] & Bitset_Adj_List[j];``                ``ans += Mask.count();``            ``}` `   ``// divide the answer by 6 to avoid duplicates``   ``ans /= 6;` `   ``cout << ``"The number of Triangles in the Graph is : "` `<< ans;``  ` `    ``// This code is contributed``    ``// by Gatea David``}`

Output

`The number of Triangles in the Graph is : 2`

Time Complexity: First we have the two for nested loops O(V2) flowed by Bitset operations & and count, both have a time complexity of O(V / Word RAM), where V = number of nodes in the graph and Word RAM is usually 32 or 64. So the final time complexity is O(V2 * V / 32) or O(V3).

```Time Complexity: O(V3)
Space Complexity: O(V2)```

References:

http://www.d.umn.edu/math/Technical%20Reports/Technical%20Reports%202007-/TR%202012/yang.pdf