Theorem (Chvátal 1975, p. 39) — every n-triangulation can be partitioned into at most ⌊n/3⌋ fans
ProvedChvatalArtGallery.FanPartition.triangulation_partition_into_fansLet and let be an -triangulation: a triangulated -gon, given by its vertices in cyclic order and a maximal set of pairwise non-crossing diagonals. Then the triangles of can be partitioned into fans with
Here a fan is a nonempty, dual-connected set of triangles of (a sub-polygon of ) having a vertex that meets all of its inner edges, and a partition into fans is a family of fans, pairwise disjoint as sets of triangles, covering every triangle of .
This is Chvátal's combinatorial theorem. Since each fan of a triangulated polygon is visible from its centre, it yields the art gallery theorem: every simple polygon with walls can be guarded by guards.
Formalization Note. The planar graph of the paper is encoded as the labelled -cycle plus a maximal set of non-crossing diagonals (the standard equivalent description of a triangulated polygon, since Mathlib has no planar embeddings). "Partitioned into fans" is made explicit as a finset of fans that are pairwise disjoint as sets of triangles and cover all triangles; fans may share vertices and edges. Fans are required to be dual-connected and to have a centre on all their inner edges; dropping either clause would trivialize or weaken the theorem. is the floor, n / 3 in ℕ. The only size hypothesis is . The geometric corollary (Klee's art gallery bound) is not part of this statement.
import Mathlib import Definitions.Def_ChvatalArtGallery_FanPartition_Triangulation
namespace ChvatalArtGallery.FanPartition
/-- Theorem (Chvátal 1975, p. 39): every n-triangulation can be partitioned into m fans where
m ≤ ⌊n/3⌋. -/
theorem triangulation_partition_into_fans (n : ℕ) (hn : 3 ≤ n) (D : Finset (Sym2 (Fin n)))
(hD : IsTriangulation n D) :
∃ P : Finset (Finset (Finset (Fin n))), IsFanPartition n D P ∧ P.card ≤ n / 3 := by sorry
end ChvatalArtGallery.FanPartition
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.