Question

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?

Answer 1

Since there is no requirement that the outer region must be a triangle, the question is not quite as trivial as indicated in earlier comments. The rectangle $[0,n] \times [0,1]$ can be triangulated by dividing it into unit squares and then inserting the SW-NE diagonal in each square. Still, this might not be the kind of grid/mesh one wants. To see the problem, it might be easier to think in terms of angles than to use Euler's polyhedron formula: If there are interior points in the triangulation, then the angles at those points have to be at least $90^\circ$ on average, while the average angle in a triangle is only $60^\circ$. It follows that most vertices of the triangulation have to be on the boundary of the region.

Answer 2

This question is too elementary for MO, but here's a hint. (See the FAQ for alternative sites to ask your question.)

1. Familiarize yourself with the notion of Euler characteristic

2. Convince yourself that the Euler characteristic of your triangulation of a rectangle is 1.

3. Deduce some inequalities on the numbers of vertices, edges and faces, assuming all faces are triangles and all vertex valences are less than or equal to 4.