compatible_labelings_empty
For any simple graph G on vertex set Fin n with decidable adjacency, compatible_labelings G ∅ = Nat.factorial n.
Statement
theorem compatible_labelings_empty {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] :
compatible_labelings G ∅ = Nat.factorial n- Source
- arXiv:2611.13571, Section 5.1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- compatible_labelingsFor a simple graph G on vertex set Fin n with decidable adjacency, and a finite set H of observed edges (H : Finset (Sym2 (Fin n))),…
Read back from the Lean
For any natural number $n$ and any simple graph $G$ on vertices Fin n with decidable adjacency, compatible_labelings G ∅ is equal to $n!$ (Nat.factorial n).
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
By definition, the compatible labelings for the empty edge set ∅ are the permutations of the vertices of G whose relabeled edge set contains ∅. Because the empty set is trivially a subset of any edge set, every permutation is compatible. The count is therefore the size of the full symmetric group on Fin n, which is n!.
The left-hand side is the number of permutations π of Fin n whose relabeled graph contains the empty edge set.
Unfolding the definition of `compatible_labelings` rewrites the quantity as the cardinality of the set of all permutations π of the vertex set Fin n satisfying ∅ ⊆ E(π(G)).
unfold compatible_labelingsEvery permutation satisfies this condition, so there are n! compatible labelings.
The condition ∅ ⊆ E(π(G)) is vacuously true for every permutation π, meaning the set of compatible labelings is the entire symmetric group Perm(Fin n). The simplifier evaluates its cardinality as n! using `Fintype.card_perm` and the fact that |Fin n| = n.
uses
Fintype.card_permsimp [Fintype.card_perm]
Fintype.card_perm- The cardinality of the permutation group of a finite type α is (card α)!.
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 number of compatible labelings for the empty observed edge set is n!. -/theorem compatible_labelings_empty {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] : compatible_labelings G ∅ = Nat.factorial n := by unfold compatible_labelings simp [Fintype.card_perm]