Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
How could you cover the plane with finitely triangles? What do you think about this kind of pattern: metafysica.nl/turing/p31m_triangulatie.gif –  Sigur Jun 29 '12 at 0:07
    
I didn't say I was covering the plane. But on a torus, for instance, it's quite easy to come up with a counter-example in which each triangle has four neighbors. I suppose one could ask for the max of the minimal number of neighbors on more complex surfaces... There must be many other ways of generalizing the problem, but I want to keep it simple to begin with. –  Yann David Jun 29 '12 at 0:20
    
You can read about triangulation of surfaces. For example: rip94550.wordpress.com/2008/08/12/… –  Sigur Jun 29 '12 at 0:24

1 Answer 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.

share|improve this answer
    
I'm under the impression that the first part of your proof could be generalized to get rid of the assumption. Assigning strictly less than three arcs to each triangle based on local considerations might be difficult though. –  Yann David Jul 4 '12 at 22:50
    
On the other hand, I don't think three edges per triangle would suffice. I don't agree with the second part: the degree sum formula would give you | E | ≥ 2n (E being G's edge set), not 4 n . –  Yann David Jul 4 '12 at 23:04
    
In fact, | E | < 2 n is an interesting, stronger version of the problem... And it seems very plausible. –  Yann David Jul 14 '12 at 16:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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