all the possible combinations to create triangles in a determined graph.

Question

Im studying about graphs.

I'm trying to get all the possible combinations to create triangles in a determined graph

For example for the complete graph $K_5$, I want to get in sage or python the $10$ triangles that I can form with adjacent matrices, where $1$ is the red edge and $0$ the main diagonal and where there is no edge.

I have tried with combinations but I only get the $120$ possible combinations where in most cases they are not triangles. example:

Code: thanks to saulspatz:

import numpy as np
from itertools import combinations

triangle = [(i,j) for i in range(5) for j in range (i+1,5)]

def matrices():
    for t in combinations(triangle,3):
        m = np.zeros((5,5))
        for c in t:
            m[c]=1
        yield m+m.transpose()

M = [m for m in matrices()]

My algorithm using matrices() is very inefficient, since it takes a lot of time for larger graphs

Answer 1

Enumerate triangles in a graph using SageMath

Let us work on the example in the question, the complete graph on five vertices.

sage: G = graphs.CompleteGraph(5)

Using subgraph_search_iterator

One way that works not only for triangles, but for any subgraph, is to use the built-in method subgraph_search_iterator.

sage: T = graphs.CycleGraph(3)
sage: triangles_a = G.subgraph_search_iterator(T)
sage: len(list(triangles_a))
60

Note that this list contains all the labeled triangles in G; so each triangle is there 6 times, for each starting vertex and each orientation.

Using edges

For the special case of triangles, one may instead iterate through edges of G, and look for common neighbours of the endpoints of edges.

sage: triangles_b = []
sage: for (i, j) in G.edges(labels=False):
....:     for k in G.neighbors(i):
....:         if k in G.neighbors(j):
....:             triangles_b.append((i, j, k))
....:
sage: len(triangles_b)
30

Here, each triangle is there three times, once for each choice of an edge of this triangle.

Using edges and comparisons

Getting each triangle only once is easy if there is a total order on vertices of G (e.g. in our example, they are integers), one can limit the enumeration above to get each triangle only once.

sage: triangles_c = []
sage: for (i, j) in G.edges(labels=False):
....:     for k in G.neighbors(i):
....:         if k > i and k > j and k in G.neighbors(j):
....:             triangles_c.append((i, j, k))
....:
sage: len(triangles_c)
10

Finally, here is the list for the example in the question:

sage: triangles_c
[(0, 1, 2),
 (0, 1, 3),
 (0, 1, 4),
 (0, 2, 3),
 (0, 2, 4),
 (0, 3, 4),
 (1, 2, 3),
 (1, 2, 4),
 (1, 3, 4),
 (2, 3, 4)]