Putnam 2007, Problem A-6

A triangulation $\mathcal{T}$ of a polygon $P$ is a finite collection of triangles whose union is $P$, and such that the intersection of any two triangles is either empty, or a shared vertex, or a shared side. Moreover, each side is a side of exactly one triangle in $\mathcal{T}$. Say that $\mathcal{T}$ is admissible if every internal vertex is shared by $6$ or more triangles. For example, [figure omitted.] Prove that there is an integer $M_n$, depending only on $n$, such that any admissible triangulation of a polygon $P$ with $n$ sides has at most $M_n$ triangles.

Solution:
For an admissible triangulation $\mathcal{T}$, number the vertices of $P$ consecutively $v_1, \ldots, v_n$, and let $a_i$ be the number of edges in $\mathcal{T}$ emanating from $v_i$; note that $a_i \geq 2$ for all $i$.

We first claim that $a_1 + \cdots + a_n \leq 4n - 6$. Let $V, E, F$ denote the number of vertices, edges, and faces in $\mathcal{T}$. By Euler's Formula, $(F+1) - E + V = 2$ (one must add 1 to the face count for the region exterior to $P$). Each face has three edges, and each edge but the $n$ outside edges belongs to two faces; hence $F = 2E - n$. On the other hand, each edge has two endpoints, and each of the $V - n$ internal vertices is an endpoint of at least 6 edges; hence $a_1 + \cdots + a_n + 6(V-n) \leq 2E$. Combining this inequality with the previous two equations gives
$$a_1 + \cdots + a_n \leq 2E + 6n - 6(1 - F + E) = 4n - 6,$$
as claimed.

Now set $A_3 = 1$ and $A_n = A_{n-1} + 2n - 3$ for $n \geq 4$; we will prove by induction on $n$ that $\mathcal{T}$ has at most $A_n$ triangles. For $n = 3$, since $a_1 + a_2 + a_3 = 6$, $a_1 = a_2 = a_3 = 2$ and hence $\mathcal{T}$ consists of just one triangle.

Next assume that an admissible triangulation of an $(n-1)$-gon has at most $A_{n-1}$ triangles, and let $\mathcal{T}$ be an admissible triangulation of an $n$-gon. If any $a_i = 2$, then we can remove the triangle of $\mathcal{T}$ containing vertex $v_i$ to obtain an admissible triangulation of an $(n-1)$-gon; then the number of triangles in $\mathcal{T}$ is at most $A_{n-1} + 1 < A_n$ by induction. Otherwise, all $a_i \geq 3$. Now the average of $a_1, \ldots, a_n$ is less than 4, and thus there are more $a_i = 3$ than $a_i \geq 5$. It follows that there is a sequence of $k$ consecutive vertices in $P$ whose degrees are $3, 4, 4, \ldots, 4, 3$ in order, for some $k$ with $2 \leq k \leq n-1$ (possibly $k = 2$, in which case there are no degree 4 vertices separating the degree 3 vertices). If we remove from $\mathcal{T}$ the $2k-1$ triangles which contain at least one of these vertices, then we are left with an admissible triangulation of an $(n-1)$-gon. It follows that there are at most $A_{n-1} + 2k - 1 \leq A_{n-1} + 2n - 3 = A_n$ triangles in $\mathcal{T}$. This completes the induction step and the proof.

**Remark:** We can refine the bound $A_n$ somewhat. Supposing that $a_i \geq 3$ for all $i$, the fact that $a_1 + \cdots + a_n \leq 4n - 6$ implies that there are at least six more indices $i$ with $a_i = 3$ than with $a_i \geq 5$. Thus there exist six sequences with degrees $3, 4, \ldots, 4, 3$, of total length at most $n+6$. We may thus choose a sequence of length $k \leq \lfloor n/6 \rfloor + 1$, so we may improve the upper bound to $A_n = A_{n-1} + 2\lfloor n/6 \rfloor + 1$, or asymptotically $\frac{1}{6}n^2$.

However (as noted by Noam Elkies), a hexagonal swatch of a triangular lattice, with the boundary as close to regular as possible, achieves asymptotically $\frac{1}{6}n^2$ triangles.