2
$\begingroup$

I am having trouble understanding a certain proof.

Claim: Every triangulation of an $n$-sided polygon has $n-2$ triangles.

Base Case ($n=3$): Trivial.

We let $P$ be a polygon with $n$ edges. A diagonal is drawn between two vertices of $P$, splitting $P$ up into two smaller polygons $a$ and $b$. Polygon $a$ has $k+1$ edges ($k$ edges of $P$ plus the diagonal), where $k$ is between $2$ and $n-2$. Then, polygon $b$ has $n-k+1$ edges ($n-k$ edges of $P$ plus the diagonal). If we apply the induction hypothesis to polygon $a$, then polygon $a$ can be broken up into $k-1$ triangles. Likewise, by applying the induction hypothesis to polygon $b$, polygon $b$ can be broken up into $n-k-1$ triangles. Putting polygons $a$ and $b$ together, we get $n-2$ triangles.

$(k-1)+(n-k-1) = n-2$ triangles.

I think my confusion arises when considering that we didn't use the induction hypothesis for $n+1$ sides. Instead, we used the induction hypothesis separately on two sub polygons of $P$.

Here's the proof I'm referencing: https://www.cise.ufl.edu/~ungor/courses/fall08/polytri.pdf

$\endgroup$
3
$\begingroup$

This is strong induction. Let $\Phi(n)$ be the statement that all triangulations of $n$-gons have $n-2$ triangles. Instead of the "weak" induction step $$\Phi(n)\implies \Phi(n+1),$$ we use $$\tag1 (\forall k\le n\colon \Phi(k))\implies \Phi(n+1).$$

The principles are equivalent: If we define $\Psi(n)\equiv \forall k\le n\colon \Phi(n)$, then we imemdiately get $\Psi(n)\implies \Psi(n+1)$ from $(1)$.


Remark: An overlooked and somewhat tricky part is hidden in your bold "A diagonal is drawn ...". It is a not fully trivial (but true) fact that every (not necessarily convex) polygon has a diagonal.

$\endgroup$
  • $\begingroup$ The link in the question leads not only to the proof that the OP is asking about but also (on the next page) to a lemma saying that every polygon has a diagonal. $\endgroup$ – Andreas Blass Jul 14 '17 at 20:54
  • $\begingroup$ But ISTM that the proof is at best incomplete, partly because there is no definition of what a "diagonal" is - at least in the two pages that I looked at. $\endgroup$ – NickD Jul 14 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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