AFTD Auto-Formalizing Theoretical Domains

compatible_labelings_empty

theoremverified

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!.

  1. 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)).

    line 4

      unfold compatible_labelings
  2. Every 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.

    line 5

    uses Fintype.card_perm

      simp [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

/-- 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]
See it in the graphDiscuss this resultChallenge it