4
$\begingroup$

Let us consider a figure of the Euclidean plane comprised of finitely many non-degenerate non-overlapping triangles (i.e., no triangle has a zero area and no two distinct triangles have any inner point in common).

Two distinct triangles are said to be neighbors iff they have at least two points in common (i.e., they share a portion of side of non-zero length, so indeed infinitely many points).

Must there be at least one triangle that has at most three neighbors?

Is this a known problem?

Thanks in advance.

  • 0
    You can read about triangulation of surfaces. For example: http://rip94550.wordpress.com/2008/08/12/triangulations-of-surfaces-minimum-number-of-triangles/2012-06-29

1 Answers 1

1

Nice question!! Here is a partial answer, under an assumption.

Assume that no two vertices of different triangles coincide in the plane.

Create a directed graph $G$, one node per triangle, as follows. If a vertex of triangle $A$ lies (necessarily on the interior of) a neighbor-relation mediating edge of triangle $B$, then add to $G$ a directed arc from $A$ to $B$. Thus every neighbor relation adds one or two arcs to $G$: one if an edge of $A$ is a subset of an edge of $B$, and two, one each direction, if an edge of $A$ partially overlaps an edge of $B$:
          Touching triangles
Each triangle can give rise to at most three arcs of $G$, because each arc consumes a vertex: $|G| \le 3n$ for $n$ triangles. The number of neighbor relations is at most the number of edges of $G$.

Suppose every triangle had at least four neighbors. Then $G$ would have $\ge 4n$ edges.

  • 0
    In fact, | _E_ | < 2 _n_ is an interesting, stronger version of the problem... And it seems very plausible.2012-07-14