Kvant Math Problem 1170

A triangulation of a convex $n$-gon contains exactly $n-3$ diagonals.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m05s
Source on kvant.digital

Problem

Consider the triangulations of a given convex $n$-gon using non-intersecting diagonals. Define a flip as the following operation: instead of a certain diagonal $BC$, which serves as a common side of two triangles $ABC$ and $BCD$ in the triangulation, we draw the diagonal $AD$ (Fig. 1). Let $P(n)$ denote the minimal number of flips required to transform any triangulation into any other. Prove the estimates:

  1. $P(n)\ge n-3$.
  2. $P(n)\le2n-7$.
  3. $P(n)\le2n-10$ for $n\ge13$.

Figure 1

D. V. Fomin

City Tournament (autumn, 1988)

Exploration

A triangulation of a convex $n$-gon contains exactly $n-3$ diagonals. A flip removes one diagonal and inserts another, so after one flip the old and new triangulations can differ in at most one diagonal. This immediately suggests the lower bound $n-3$: if two triangulations have no common diagonal, then all $n-3$ diagonals must eventually be replaced.

For the upper bounds, a natural strategy is to choose a distinguished vertex $A$ and transform every triangulation into the fan centered at $A$, namely the triangulation consisting of all diagonals from $A$ to the nonadjacent vertices. If every triangulation can be transformed into that fan in at most $n-4$ flips, then any two triangulations can be connected through the fan in at most $2(n-4)=2n-8$ flips. This is close to the desired estimate but not quite enough.

Let $d(A)$ be the number of diagonals of the triangulation incident with $A$. In the fan, $d(A)=n-3$. If $d(A)<n-3$, there exists a triangle of the triangulation whose two sides are boundary edges not containing $A$. Such a triangle can be used to perform a flip increasing $d(A)$ by $1$. Repeating, one reaches the fan in exactly $n-3-d(A)$ flips.

Thus the distance from a triangulation to the fan equals $n-3-d(A)$. If two triangulations are transformed through the same vertex $A$, the number of flips is

$$2(n-3)-d_1(A)-d_2(A),$$

where $d_1,d_2$ are the corresponding degrees.

To obtain $2n-7$, it suffices to find a vertex $A$ with $d_1(A)+d_2(A)\ge1$. Every triangulation has at least one diagonal, hence some vertex is incident with a diagonal, so choosing such a vertex in one triangulation gives the result.

For $2n-10$, one needs a vertex with $d_1(A)+d_2(A)\ge4$. Since a triangulation has $n-3$ diagonals and each diagonal contributes $2$ to the sum of the degrees,

$$\sum_v d(v)=2(n-3).$$

Hence the average degree equals $2-\frac6n$. For $n\ge13$ this average exceeds $\frac32$. If for every vertex we had $d_1(v)+d_2(v)\le3$, then summing over all vertices would give

$$4(n-3)=\sum_v(d_1(v)+d_2(v))\le3n,$$

which is impossible for $n\ge13$ because $4n-12>3n$. Therefore some vertex satisfies $d_1(v)+d_2(v)\ge4$, yielding the stronger estimate.

The step most likely to hide an error is the claim that one can always increase $d(A)$ by one flip whenever $d(A)<n-3$. This requires a precise geometric argument.

Problem Understanding

We are given the graph whose vertices are triangulations of a fixed convex $n$-gon and whose edges correspond to flips. Let $P(n)$ be the largest possible distance between two triangulations, equivalently the smallest number such that any two triangulations can be connected by at most $P(n)$ flips.

The problem is of Type B. We must prove three bounds:

$$P(n)\ge n-3,$$

$$P(n)\le2n-7,$$

and, for $n\ge13$,

$$P(n)\le2n-10.$$

The core difficulty is to estimate how many flips are needed to transform an arbitrary triangulation into a canonical one, and then to choose the canonical vertex cleverly enough to improve the bound.

Proof Architecture

Lemma 1. There exist two triangulations of an $n$-gon having no common diagonal.

Sketch. Use the two fans centered at adjacent vertices; every diagonal of one fan contains one center, every diagonal of the other contains the other center.

Lemma 2. Fix a vertex $A$. Any triangulation can be transformed into the fan centered at $A$ in exactly $n-3-d(A)$ flips, where $d(A)$ is the number of diagonals incident with $A$.

Sketch. Show that whenever $d(A)<n-3$, there exists a flip increasing $d(A)$ by one; iterate until the fan is reached.

Lemma 3. For any two triangulations $T_1,T_2$ and any vertex $A$, the distance between them is at most

$$2(n-3)-d_1(A)-d_2(A).$$

Sketch. Transform both triangulations to the fan centered at $A$.

Lemma 4. Every triangulation satisfies

$$\sum_v d(v)=2(n-3).$$

Sketch. Count incidences between vertices and diagonals.

The hardest lemma is Lemma 2, because it requires proving the existence of a flip that increases the degree of the chosen vertex.

Solution

Let $Q$ be a convex $n$-gon.

For a triangulation $T$ and a vertex $A$ of $Q$, denote by $d_T(A)$ the number of diagonals of $T$ incident with $A$.

First we prove the lower bound.

Consider two adjacent vertices $A$ and $B$ of the polygon. Let $F_A$ be the fan triangulation consisting of all diagonals issuing from $A$, and let $F_B$ be the fan triangulation consisting of all diagonals issuing from $B$.

Every diagonal of $F_A$ has endpoint $A$, while every diagonal of $F_B$ has endpoint $B$. Since $A$ and $B$ are adjacent, no diagonal can have both endpoints $A$ and $B$. Hence $F_A$ and $F_B$ have no common diagonal.

A flip changes exactly one diagonal. Since a triangulation contains $n-3$ diagonals, any sequence transforming $F_A$ into $F_B$ must replace all $n-3$ diagonals. Consequently at least $n-3$ flips are necessary. Therefore

$$P(n)\ge n-3.$$

Now fix a vertex $A$.

We shall show that any triangulation $T$ can be transformed into the fan centered at $A$ in exactly $n-3-d_T(A)$ flips.

If $d_T(A)=n-3$, then every possible diagonal from $A$ is present, so $T$ already is the fan.

Assume $d_T(A)<n-3$. Then not all diagonals from $A$ are present. Consider all triangles of the triangulation not containing $A$. Their union is a polygonal region. Since this region is nonempty, it has a boundary edge lying on the boundary of $Q$. Choose a triangle $BCD$ of the triangulation having two sides $BC$ and $CD$ on the boundary of $Q$ and not containing $A$.

The quadrilateral formed by the two triangles adjacent to the diagonal $BD$ has vertices $A,B,C,D$ in cyclic order. The diagonal of this quadrilateral belonging to the triangulation is $BD$. Flipping $BD$ replaces it by $AC$.

Before the flip, neither $BD$ nor $AC$ is incident with $A$; after the flip, the new diagonal $AC$ is incident with $A$. Thus

$$d_T(A)$$

increases by $1$.

Repeating this operation, we increase $d_T(A)$ by one at each step until it reaches $n-3$. At that moment the triangulation is the fan centered at $A$. Since the degree increases from $d_T(A)$ to $n-3$, exactly

$$n-3-d_T(A)$$

flips are used.

Let $T_1$ and $T_2$ be two triangulations. Transform both to the fan centered at $A$. The first transformation requires

$$n-3-d_{T_1}(A)$$

flips and the second requires

$$n-3-d_{T_2}(A)$$

flips. Reversing the second transformation gives a path from $T_1$ to $T_2$ of length

$$2(n-3)-d_{T_1}(A)-d_{T_2}(A).$$

Hence

$$\operatorname{dist}(T_1,T_2) \le 2(n-3)-d_{T_1}(A)-d_{T_2}(A).$$

To prove the estimate $P(n)\le2n-7$, choose a vertex $A$ incident with some diagonal of $T_1$. Such a vertex exists because every triangulation of an $n$-gon with $n\ge4$ contains at least one diagonal. Then

$$d_{T_1}(A)\ge1, \qquad d_{T_2}(A)\ge0.$$

Therefore

$$\operatorname{dist}(T_1,T_2) \le 2(n-3)-1 = 2n-7.$$

Since $T_1$ and $T_2$ were arbitrary,

$$P(n)\le2n-7.$$

For the stronger estimate, let

$$d_1(v)=d_{T_1}(v),\qquad d_2(v)=d_{T_2}(v).$$

Each diagonal contributes $1$ to the degree of each of its two endpoints. Since a triangulation has $n-3$ diagonals,

$$\sum_v d_i(v)=2(n-3), \qquad i=1,2.$$

Adding the two equalities,

$$\sum_v\bigl(d_1(v)+d_2(v)\bigr)=4(n-3).$$

Suppose every vertex satisfied

$$d_1(v)+d_2(v)\le3.$$

Then

$$4(n-3)\le3n.$$

For $n\ge13$ this is impossible, because

$$4(n-3)=4n-12>3n.$$

Hence there exists a vertex $A$ such that

$$d_1(A)+d_2(A)\ge4.$$

Using the distance estimate already proved,

$$\operatorname{dist}(T_1,T_2) \le 2(n-3)-4 = 2n-10.$$

Since $T_1$ and $T_2$ were arbitrary,

$$P(n)\le2n-10 \qquad (n\ge13).$$

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the existence of a flip increasing $d_T(A)$.

Assume $d_T(A)<n-3$. Then some diagonal from $A$ is missing, so the triangulation is not the fan. The triangles not containing $A$ form a nonempty connected region. A boundary triangle of this region has two sides on the boundary of the original polygon; call it $BCD$. The side opposite $C$ is a diagonal $BD$. The second triangle adjacent to $BD$ contains $A$, because $BCD$ lies on the boundary of the region of triangles not containing $A$. Thus the surrounding quadrilateral is $ABCD$, and the flip replaces $BD$ by $AC$. Exactly one new diagonal incident with $A$ appears, so the degree increases by one.

The second delicate point is the derivation of the distance estimate. The argument does not require that the path through the fan be shortest. It merely constructs a path of length

$$(n-3-d_1(A))+(n-3-d_2(A)).$$

Since graph distance is at most the length of any explicit path, the inequality follows.

The third delicate point is the averaging argument for $n\ge13$. The contradiction uses

$$\sum_v(d_1(v)+d_2(v))=4(n-3).$$

If every summand were at most $3$, the sum would be at most $3n$. The inequality

$$4(n-3)>3n$$

is equivalent to $n>12$, exactly the stated range. No stronger conclusion is needed.

Alternative Approaches

A different route is to interpret a triangulation as a rooted binary tree. A flip corresponds to a tree rotation. The fan triangulation becomes a path-like tree. One can then estimate the diameter of the rotation graph by counting how many rotations are needed to move every internal node toward the root. This yields bounds of the same order, although translating the argument back to polygon triangulations requires additional notation.

The geometric fan method is preferable because the quantity $d_T(A)$ provides an explicit potential function. Each flip can be chosen to increase this potential by exactly one, giving a direct count of the number of flips needed to reach the fan and making both upper bounds immediate consequences of degree estimates.