6
$\begingroup$

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$:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Is it possible to draw more edges between not connected nodes? Or do we have to use only the already drawn edges? $\endgroup$ – zar Jun 19 '18 at 9:35
  • 2
    $\begingroup$ I think that case IIIb should be 5: you have 5 diagonals, and for each diagonal you have one triangle. $\endgroup$ – zar Jun 19 '18 at 9:38
  • $\begingroup$ @zar It seems that you're indeed right. I have overcounted the number of triangles in case III b by a factor of $2$. :) $\endgroup$ – stressed out Jun 19 '18 at 9:43
  • $\begingroup$ I don't understand one point: is this a legal triangle? imgur.com/a/O0TjspH $\endgroup$ – zar Jun 19 '18 at 9:52
  • $\begingroup$ @zar No. That's not a legal triangle because the edge you have used is not one of the edges on the picture. You have altered the picture in other words and that's not allowed. $\endgroup$ – stressed out Jun 19 '18 at 9:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I just wanted to let you know that I have seen your answer but I need some more time to analyze it and I understand it. :) $\endgroup$ – stressed out Jun 19 '18 at 13:18
  • 2
    $\begingroup$ In the second case, the possibilites "ab,ad,ce" and "ac,ae,bd" would lead to one of the intersections lying outside the original convex polygon, so I don't think they count. $\endgroup$ – Henning Makholm Jul 8 '18 at 17:26
  • $\begingroup$ @HenningMakholm thanks! Not sure what I was thinking there, but you're right, there is only one option (up to cyclic permutation) for five endpoints. Will edit accordingly. $\endgroup$ – Especially Lime Jul 10 '18 at 11:58
0
$\begingroup$

The problem with the node approach here is that not all $3$ nodes produce a triangle. Counting up all the exclusions can be more complex than just counting triangles. I often use a systematic approach based on single, double, triple triangles, and in this case including the inner pentagon plus $2$ triangles and inner pentagon plus $4$ triangles. For these $5$ cases........

Single, $= 10$

Double, $= 10$

Triple, $= 5$

Inner Pent $+ 2, = 5$

Inner Pent $+ 4, = 5$

Total, $= 35$

$\endgroup$
  • $\begingroup$ Dear Phil, the node approach, even though tricky, works fine in this particular case. Moreover, your answer is an undercount. The correct answer is $35$. $\endgroup$ – stressed out Jul 8 '18 at 3:47
  • $\begingroup$ Hmm, the best system in the world doesn't work if you can't count. There should be 10 double triangles not 8. $\endgroup$ – Phil H Jul 8 '18 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.