How to find all triangles in a graph

Question

I am looking for a computationally-efficient method to generate a complete list of the triangles in a given graph. For the purposes of this question, we give each vertex a letter name, and a triangle is recorded by writing the three letters. Although the order of the letters does not matter, only one of the possible orders should be recorded (i.e. you may record "EFA", "FEA", "AFE", "FAE", "EAF", or "AEF", but only one of them).

Each vertex has a reference to every other vertex. The algorithm starts with a single vertex, which is assumed to be connected in some way to every other point in the graph. For instance, if we started with E in the example image, we could then move to F, A, or B and continue until we record every triangle in the graph.

A triangle is defined as a group of three vertices that are connected to each other, but do not contain any points within them. In the example graph, while ABD, ACD, and BDC are all triangles, ABC is not. (In this case, the complete set of triangles is EAB, EAF, AFG, AGC, ADB, ADC, BDC.)

For my particular purposes, the graph happens to have the assumption that every enclosed shape in the graph is a triangle. For instance, in this example, removing the edge AB would make the graph invalid, since EBDA would be a quadrilateral. Also, there are no "hanging" edges - every edge borders at least one triangle. A graph that does not meet these conditions does not need to be considered.

Answer 1

Enumerate edges and make sure that end points of each edge are listed in alphabetical order. The following program will simply go through the list of edges, check if they have a common point and if they do, it will check if the remaining two points also constitute an edge in the input set.

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('A', 'D'),
    ('A', 'E'),
    ('A', 'F'),
    ('A', 'G'),
    ('B', 'C'),
    ('B', 'D'),
    ('B', 'E'),
    ('C', 'D'),
    ('C', 'G'),
    ('E', 'F'),
    ('F', 'G')
]

for i in range(0, len(edges) - 1):
    for j in range(i + 1, len(edges)):
        e1 = edges[i]
        e2 = edges[j]
        if e1[0] == e2[0]:
            if (e1[1], e2[1]) in edges:
                print(e1[0] + e1[1] + e2[1])
        else:
            break

The program prints:

ABC
ABD
ABE
ACD
ACG
AEF
AFG
BCD

Answer 2

Many software systems permit such a search. In Mathematica:

g = Graph[{"E" <-> "A", "E" <-> "B", "E" <-> "F", "A" <-> "F", 
   "F" <-> "G", "G" <-> "C", "A" <-> "C", "A" <-> "D", "D" <-> "C", 
   "B" <-> "D", "A" <-> "B", "B" <-> "C"}, VertexLabels -> Automatic]

Find all cycles of length exactly $3$:

FindCycle[g, {3}, All]

{{"A" <-> "C", "C" <-> "D", "D" <-> "A"}, 
 {"B" <-> "D", "D" <-> "C", "C" <-> "B"}, 
 {"A" <-> "C", "C" <-> "B", "B" <-> "A"}, 
 {"A" <-> "D", "D" <-> "B", "B" <-> "A"}, 
 {"E" <-> "B", "B" <-> "A", "A" <-> "E"}, 
 {"E" <-> "A", "A" <-> "F", "F" <-> "E"}}

Length[%]

(* 6 *)

There are six of them.

GraphicsGrid[
 Partition[(HighlightGraph[g, #] & /@ FindCycle[g, {3}, All]), 3]]

The above is the solution for a true graph, where the layout ("embedding") is not essential.