1
$\begingroup$

What is the maximal number of triangles in a planar graph with $n$ points?

Here by triangle I mean any closed path of length 3 (so a triangle can also include in the interior points other than the vertices).
For example, it is easy to see that the answer is 4 for $n=4$ and 7 for $n=5$.

VERY IMPORTANT EDIT: At the beggining, the question was for coplanar graphs. But I changed it to planar graphs now.

$\endgroup$
  • 4
    $\begingroup$ Every problem about coplanar graphs is in principle solved. See the paper by Cvetković. $\endgroup$ – LeechLattice Aug 9 '19 at 15:42
  • $\begingroup$ It's just a way to say that the OP wants 3-cycles, not necessarily faces of size 3. For example, if you draw a "triangle" a-b-c (by Fàry's theorem we can suppose rectilinear edges) and then you add several more vertices and arcs, you still want to count abc as a triangle, even though is not necessarily a 3-face $\endgroup$ – Luca Ghidelli Aug 9 '19 at 15:59
  • $\begingroup$ I will check later, but to me the answer for planar graphs seems to be 3n-8. Since for all n<9 it is possible to show examples of coplanar graphs with this bound, I would say that the answer is 3n-8 for them as well. $\endgroup$ – Luca Ghidelli Aug 9 '19 at 17:17
  • $\begingroup$ Important Edit: At the beggining, the question was for coplanar graphs. But I changed it to planar graphs now. I also strongly believe that the answer is $3n-8$ for this version. $\endgroup$ – İbrahim Suat Evren Aug 10 '19 at 9:42
  • 3
    $\begingroup$ You really shouldn't change a question like this. It makes comments and answers obsolete and readers get confused. You should start a new question. $\endgroup$ – Brendan McKay Aug 10 '19 at 10:59
11
$\begingroup$

The maximum occurs for a triangulation, since the count can only increase if edges are added without destroying planarity. Note that not all triangulations have the same number of triangles since they may not all be faces.

In a few milliseconds of cpu time:

Max for n=3: 1
Max for n=4: 4
Max for n=5: 7
Max for n=6: 10
Max for n=7: 13
Max for n=8: 16

There are no coplanar graphs for $n\ge 9$.

For planar graphs not necessarily coplanar, the maximum is $3n-8$ for $n\ge 3$ and there is an easy construction making all of them. See Apollonian network.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, $3n-8$, as Luca suspected. $\endgroup$ – Gerry Myerson Aug 9 '19 at 22:55
  • $\begingroup$ The proof that I had in mind was: (1) wlog the graph is a triangulation (2) wlog there is a vertex of degree 3 (3) induction. To prove (2) I oserved that under some conditions it is possible to replace two triangle faces abc+bcd into abd+adc without decreasing the total number of 3-cycles. $\endgroup$ – Luca Ghidelli Aug 10 '19 at 13:21
  • $\begingroup$ @LucaGhidelli There might not be a vertex of degree 3, or even 4. $\endgroup$ – Brendan McKay Aug 10 '19 at 15:46
  • $\begingroup$ I know, the average degree is just a little less than 6. But you can create one such vertex with the move that I wrote (some care is required, but nothing much difficult). So at the end of the day you, for the sake of maximality, you can assume there is a vertex of degree 3. In fact this is true a posteriori: every Apollonian network has a vertex of degree 3. In fact this proof can be used to characterize them in this way. $\endgroup$ – Luca Ghidelli Aug 10 '19 at 23:30
  • 1
    $\begingroup$ Now I see where is a possible ambiguity. When I wrote "To prove (2) ..." I did not mean that I prove there is a vertex of degree 3. But I mean to prove that 'wlog there is a vertex of degree 3'. Looking closely in the proof, I actually do prove that a planar graph realizing the maximal number of 3-cycles (1) is a triangulation (2) has a vertex of degree 3. However, before I actually wrote something weaker: (1) wlog=without loss of generality... (2) wlog..., hope it's more clear now. $\endgroup$ – Luca Ghidelli Aug 10 '19 at 23:37

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.