palette_degree_le_card_univ
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.
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).
unfold palette_degreeThe 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).
uses
le_trans,Finset.card_filter_le,Finset.card_le_univexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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 _)