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.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Every problem about coplanar graphs is in principle solved. See the paper by Cvetković. $\endgroup$
    – LeechLattice
    Commented Aug 9, 2019 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
    Commented Aug 9, 2019 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
    Commented Aug 9, 2019 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$
    – user144177
    Commented Aug 10, 2019 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
    Commented Aug 10, 2019 at 10:59

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ So, $3n-8$, as Luca suspected. $\endgroup$
    – Gerry Myerson
    Commented Aug 9, 2019 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
    Commented Aug 10, 2019 at 13:21
  • $\begingroup$ @LucaGhidelli There might not be a vertex of degree 3, or even 4. $\endgroup$
    – Brendan McKay
    Commented Aug 10, 2019 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
    Commented Aug 10, 2019 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
    Commented Aug 10, 2019 at 23:37

You must log in to answer this question.