How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
For and a triangulation of the -gon there is a unique with such that and are both chords of or sides, and splits along
Statement
Let and let be a triangulation of the labelled -gon.
Then there is a unique index with such that both and are sides or diagonals of the triangulation. Equivalently, the closing side lies in a unique triangle with third vertex .
For that index :
- every diagonal of has both endpoints in or both endpoints in ;
- the restriction of to is a triangulation of the -gon;
- the restriction of to is a triangulation of the -gon.
Facts & Assumptions
Given: a natural number and a triangulation .
A triangulation is a maximal set of pairwise non-crossing diagonals of the labelled polygon (Chords of a labelled convex polygon, crossing, and triangulations, defined combinatorially).
Proof
Let be the least element of such that is a diagonal of or the side . This set is nonempty because belongs to it.
The chord is a side or lies in . If it were a diagonal outside , maximality would give a diagonal crossing it, so ; if then would cross , impossible, and if then would contradict the minimality of .
Every diagonal of has both endpoints in or both endpoints in . Indeed, if had , then it would cross ; and if , then would satisfy the defining property of step 1.1 with , again impossible.
The diagonals of with endpoints in form a triangulation of the -gon, and those with endpoints in form a triangulation of the -gon: they are pairwise non-crossing because they are diagonals of , and they are maximal because any extra diagonal in one sub-polygon would also be a diagonal of the whole polygon and would not cross any member of by step 3.1. The index is unique, for if another index with had the same property, then the chords and would cross when , or the symmetric crossing would occur when .
Remarks
- This is the polygon version of first return. The closing side plays the role of the root edge, and the third vertex is the split point.
Depends on
- Chords of a labelled convex polygon, crossing, and triangulations, defined combinatorially
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
- The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$, and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$
Used by
Dependency tree · two levels
23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- D. Guichard, An Introduction to Combinatorics and Graph Theory, Exercise 3.5.5 (standard reference, not scraped)