Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem (Chvátal 1975, p. 39) — every n-triangulation can be partitioned into at most ⌊n/3⌋ fans

Proved
ChvatalArtGallery.FanPartition.triangulation_partition_into_fans

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

art-gallerycombinatoricsfanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1triangulation

Let n≥3n \ge 3n≥3 and let GGG be an nnn-triangulation: a triangulated nnn-gon, given by its vertices 0,…,n−10,\dots,n-10,…,n−1 in cyclic order and a maximal set DDD of pairwise non-crossing diagonals. Then the triangles of GGG can be partitioned into mmm fans with

m≤⌊n3⌋.m \le \left\lfloor \frac{n}{3} \right\rfloor .m≤⌊3n​⌋.

Here a fan is a nonempty, dual-connected set of triangles of GGG (a sub-polygon of GGG) 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 GGG.

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 nnn walls can be guarded by ⌊n/3⌋\lfloor n/3\rfloor⌊n/3⌋ guards.

Formalization Note. The planar graph of the paper is encoded as the labelled nnn-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 mmm fans" is made explicit as a finset PPP 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. [n/3][n/3][n/3] is the floor, n / 3 in ℕ. The only size hypothesis is n≥3n \ge 3n≥3. The geometric corollary (Klee's art gallery bound) is not part of this statement.

Preamble
import Mathlib
import Definitions.Def_ChvatalArtGallery_FanPartition_Triangulation
Formal statement
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
Source
Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B 18 (1975), p. 39, Theorem ("Every n-triangulation can be partitioned into m fans where m ≤ [n/3].")
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me