AFTD Auto-Formalizing Theoretical Domains

palette_degree_le_card_univ

theoremverified

For a finite type V, a simple graph G on V, a natural number k, a palette system P : V → Finset (Fin k), a vertex v : V, and a color i : Fin k, the palette degree palette_degree G P v i is at most Fintype.card V.

Statement

theorem palette_degree_le_card_univ {V : Type*} [Fintype V] (G : SimpleGraph V) {k : ℕ} (P : V → Finset (Fin k)) (v : V) (i : Fin k) : palette_degree G P v i ≤ Fintype.card V
Source
arXiv:2610.31489, Section 2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • palette_degreeGiven a finite type V, a simple graph G on V, a natural number k, a palette system P : V → Finset (Fin k), a vertex v : V, and a color i :…

Read back from the Lean

For every finite type $V$, every simple graph $G$ on $V$, every natural number $k$, every function $P : V \to \mathrm{Finset}(\mathrm{Fin}\ k)$, every vertex $v \in V$, and every index $i \in \mathrm{Fin}\ k$, the palette degree of $v$ with respect to $P$ and $i$ (palette_degree G P v i) is less than or equal to the cardinality of $V$ (Fintype.card V).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof unfolds the definition of palette degree as the cardinality of the set of neighbors whose palette contains the given color. It then chains two inequalities via transitivity: the size of a filtered subset of neighbors is at most the number of neighbors, which is at most the total number of vertices in the graph.

  1. The goal reduces to showing that the size of the filtered neighbor set is at most the cardinality of V.

    Expanding the definition of palette_degree, the palette degree of v with respect to color i is by definition the cardinality of the set of neighbors u of v such that i ∈ P(u).

    line 3

      unfold palette_degree
  2. The palette degree is at most the total number of vertices in V.

    By transitivity of inequality (le_trans), the size of the filtered set of neighbors is bounded above by the cardinality of the neighbor set itself (via Finset.card_filter_le), which is in turn bounded above by the total number of vertices in the type V (via Finset.card_le_univ).

    line 4

    uses le_trans, Finset.card_filter_le, Finset.card_le_univ

      exact le_trans (Finset.card_filter_le _ _) (Finset.card_le_univ _)
le_trans
for any preorder, if a ≤ b and b ≤ c, then a ≤ c
Finset.card_filter_le
filtering a finite set by a predicate produces a subset whose cardinality is at most that of the original set
Finset.card_le_univ
the cardinality of any finite subset of a finite type is at most the cardinality of the entire type

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The palette degree of any vertex is at most the total number of vertices in the graph. -/theorem palette_degree_le_card_univ {V : Type*} [Fintype V] (G : SimpleGraph V) {k : ℕ} (P : V → Finset (Fin k)) (v : V) (i : Fin k) : palette_degree G P v i ≤ Fintype.card V := by  unfold palette_degree  exact le_trans (Finset.card_filter_le _ _) (Finset.card_le_univ _)
See it in the graphDiscuss this resultChallenge it