AFTD Auto-Formalizing Theoretical Domains

facial_distinguishing_labeling_monotone

theoremverifiedoriginal

For any simple graph G on Fin n with decidable adjacency, dart permutation σ, and natural numbers k ≤ k', if G admits an adjacent-facial-sum-distinguishing proper vertex labeling with bound k, then G admits an adjacent-facial-sum-distinguishing proper vertex labeling with bound k'.

Statement

theorem facial_distinguishing_labeling_monotone {n : ℕ} (G : SimpleGraph (Fin n))
    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) {k k' : ℕ} (h : k ≤ k')
    (h_label : simple_graph_has_facial_distinguishing_labeling G σ k) :
    simple_graph_has_facial_distinguishing_labeling G σ k'
Related work
arXiv:2611.18384 Sec. 2.1
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_has_facial_distinguishing_labelingA simple graph G on Fin n with decidable adjacency and dart permutation σ admits an adjacent-facial-sum-distinguishing proper vertex…
  • simple_graph_face_sumGiven a simple graph G on Fin n with decidable adjacency, a permutation σ of G.Dart, a vertex weighting c : Fin n → ℕ, and a dart d :…

Read back from the Lean

Let $n$ be a natural number, $G$ a simple graph on vertex set $\mathrm{Fin}\ n$ with decidable adjacency, and $\sigma$ a permutation of the darts of $G$. For any natural numbers $k$ and $k'$ such that $k \le k'$, if $G$ admits a facial distinguishing labeling with parameter $k$ with respect to $\sigma$, then $G$ also admits a facial distinguishing labeling with parameter $k'$ with respect to $\sigma$.

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

Lean source view module on GitHub

/-- Monotonicity of adjacent-facial-sum-distinguishing labelings with respect to the label bound k. -/
theorem facial_distinguishing_labeling_monotone {n : ℕ} (G : SimpleGraph (Fin n))
    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) {k k' : ℕ} (h : k ≤ k')
    (h_label : simple_graph_has_facial_distinguishing_labeling G σ k) :
    simple_graph_has_facial_distinguishing_labeling G σ k' := by
  obtain ⟨c, hproper, hsum⟩ := h_label
  refine ⟨fun v => Fin.castLE (Nat.succ_le_succ h) (c v), ?_, ?_⟩
  · intro u v huv
    have := hproper u v huv
    simpa using this
  · intro d
    have key : (fun v => ((fun v => Fin.castLE (Nat.succ_le_succ h) (c v)) v : ℕ)) =
        (fun v => (c v : ℕ)) := by
      funext v
      simp
    rw [key]
    exact hsum d
See it in the graphDiscuss this resultChallenge it