So, my cousin asked me to count the number of triangles in a picture. The picture was the complete graph on $5$ vertices, known as $K_5$ in graph theory. Here's a "picture" of $K_5$:
A partial answer has been given here on MSE in this question which can be wrong depending on the interpretation of what a "node" is. In our interpretation of the problem, the intersection of two edges forms a new node. So, the points of intersection inside the pentagon lying on the edges of the inner star are considered nodes on their own and therefore, the formula given in that answer is indeed an undercount for our problem.
I reasoned like this:
Case I – triangles formed by all the three vertices on the pentagon: This is
given by ${5 \choose 3}=10$
Case II – triangles with exactly one vertex on the pentagon: You see that in this case, the only way to form a triangle is to select the two other vertices on the inner star adjacent to our initial vertex on the pentagon. In this case since we have $5$ vertices, we get $5$ different triangles.
Case III – triangles with exactly two vertices on the pentagon:
I wish I could draw a picture for this case but I don't know how to do that. Anyway, in this case, we'll have $2$ separate cases:
a) The two vertices are adjacent to each other: In this case, we get $3$ non-equivalent triangles. How many ways can we choose two adjacent vertices on the pentagon? $5$ ways. Therefore, we get $15$ triangles.
b) The two vertices are not adjacent to each other: In this case, choosing two non-adjacent vertices gives us a triangle each time. For a fixed vertex on the pentagon, we can choose two non-adjacent vertices. Therefore, we get $10$ triangles this time. (This is wrong, please read my edit and the comments under the question.)
I would highly appreciate a fancy solution that uses a combination of graph theory and group theory. I believe there should be an answer like that and if you have one, please post it with explanations.
EDIT: As noted by zar, it seems that I have overcounted the number of triangles in case III b by a factor of two because after I choose a diagonal of the pentagon, I get a unique triangle. Of course, If I instead focus on the vertices on the pentagon, two vertices joined by a diagonal of the pentagon give rise to the same triangle in case III b and that's why I have overcounted by a factor of $2$. I still appreciate a systematic solution using recurrence relations, graph theory, group theory or anything that gives more mathematical insight and maybe can be generalized to problems involving $p$-gons.
Best Answer
There are at least two different ways to extend this problem to larger $n$. Here's an approach which works for the easier of the two ways, which is where the vertices of $K_n$ are $n$ points in general position forming a convex $n$-gon, so every internal node is on exactly two edges.
Every triangle can be associated with a triple of distinct edges of $K_n$ (the edges you get if you extend the sides of the triangle as far as possible), and each triple of edges is associated with at most one triangle. So we just need to count the "good" triples which do give a triangle, i.e. every pair of edges meets (either at a vertex of the original graph or at an internal node).
Suppose we know the set of endpoints of a good triple of edges (without multiplicity): how many good triples have exactly those endpoints? If there are six points in the set, $a,b,c,d,e,f$ in cyclic order, there is only one good triple consisting of the edges $ad,be,cf$. If we have five endpoints, $a,b,c,d,e$ in cyclic order, there is exactly one point in two of the edges. Suppose it is $a$. Then the only possibility is $ac,ad,be$ (thanks to Henning Makholm for pointing out that my other "possibilities" weren't valid). Since the choice of $a$ was arbitrary, there are $5$ possibilities in total. If there are four points $a,b,c,d$ in the set, the only possibilities are $ab,bd,ac$ and cyclic rearrangements. Finally, if there are only three points there is only one possibility.
This means the number of triangles is $\binom n6+5\binom n5+4\binom n4+\binom n3$.
To deal with the other plausible extension (the vertices form a regular $n$-gon) you'd need to calculate the number of degenerate triangles arising from three diagonals which all meet at a point, and subtract them off.