How many triangles from a set of pairs? I have a set of of pairs that looks like this [{a,b},{c,b},{d,f},{d,b},{a,d},{c,e},{a,f},...].
I need to find out which and how many of those pairs can be connected into a triangle. The order doesn't matter.
One possible solution would for example be [{d,f},{a,d},{a,f}], because those are the 3 sides to the triangle △FDA.
I've mocked up this little picture to better illustrate the problem:

I'm actually sitting over this problem for days now, but any idea I came up with, I had to discard.
There's no guarantee that these triangles can be built from the pairs in any way. The set is allowed to have a non-infinite, chaotic number of pairs.
 A: If you represent your graph as an adjacency matrix $A$, where $A_{ij}$ represents the number of edges that go from node $i$ to node $j$, then let $P=A^n$, $P_{ij}$ represents the number of paths of length $n$ from $i$ to $j$. From $P$, we can see that the main diagonal has paths of length three that start and end at the same vertex, which is exactly what you're looking for. So we add up all the elements of the main diagonal (also known as the trace of a graph). However, for any triangle, this sum will count it six times over because we would count $ADF$ as $ADF,\ AFD,\ DAF,\ DFA,\ FAD,\text{ and } FDA$. This is easy enough to fix, we just divide the sum by six.
Formally, the exact equation is $\text{trace}(A^3)/6$, where $A$ is the adjacency matrix.
Here is a more detailed explanation.
A: There is a straightforward solution: simply go over every possible way to choose three edges and check if they form a triangle.
A simple potential improvement over this is to instead get the list of all1 vertices and go over every possible way to choose three vertices and check if they form a triangle.
This variation definitely requires that you store edges in a data structure that allows efficient membership tests (e.g. a hash table; in python you could use an instance of set). 
1: Actually, I mean just the vertices incident with at least one edge 

If it turns out that the straightforward approach doesn't meet your actual needs, here is an alternative.
First, for every vertex $A$, construct the list $\mathrm{Adjacent}(A)$ whose elements are all vertices adjacent to $A$.
(it's likely you will want to build all the lists in one loop where you go over each edge and update the two vertex lists)
Next, for every vertex $A$, you do the following. You search through all pairs of elements $B,C \in \mathrm{Adjacent}(A)$, and check if the edge $BC$ is in your set of edges.
(again you want the edges in a structure that allows efficient membership testing)
This algorithm finds each triangle three times. You can avoid redundant work by ordering the vertices. Then, for example, for each $A$, you might search only over the pairs $B,C \in \mathrm{Adjacent}(A)$ for which both vertices are larger than $A$.
(another possibility that might be even better is to search over $B$ less than $A$ and $C$ greater than $A$)

Another way to use these lists is the following algorithm:


*

*Iterate over every edge $AB$


*

*Compute the intersection $\mathrm{Adjacent}(A) \cap \mathrm{Adjacent}(B)$



Every vertex $C$ in the intersection will yield a triangle $ABC$.
There are a number of ways to compute intersections of lists. One generic method is if you have a way to sort vertices. Then make sure every list is sorted, and you can find the intersection by iterating through both lists. (in just one pass through)
This also benefits from the trick of the previous section to avoid doing redundant work.
