AFTD Auto-Formalizing Theoretical Domains

ColoredRootedTree

structure

A finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices, linearly ordered ancestor sets, and adjacent nodes having different colors.

Statement

structure ColoredRootedTree
Defined in
arXiv:2611.03620 Section 2.1
Verified
05 Nov 2026
Axioms
none listed
Used by 14

Read back from the Lean

The structure ColoredRootedTree defines a 4-colored finite rooted tree poset, consisting of: - A type V of vertices; - Typeclass instances [Fintype V], [DecidableEq V], and [PartialOrder V] providing finiteness, decidable equality, and a partial order ≤ on V; - A designated vertex root : V; - An axiom bot_le : ∀ v : V, root ≤ v, asserting that root is a least element of the poset; - An axiom down_chain : ∀ u₁ u₂ v : V, u₁ ≤ v → u₂ ≤ v → u₁ ≤ u₂ ∨ u₂ ≤ u₁, asserting that the set of predecessors of any vertex v forms a chain (total order); - A coloring function color : V → Fin 4; - An axiom proper_coloring : ∀ u v : V, u < v → (∀ w : V, u ≤ w → w < v → w = u) → color u ≠ color v, asserting that if v covers u in the poset order (i.e., u < v with no element strictly between them, representing a directed edge from parent u to child v), then u and v receive distinct colors.

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

/-- A finite rooted tree properly 4-colored, structured as an ancestorship poset. -/
structure ColoredRootedTree where
  V : Type
  [fintype : Fintype V]
  [decEq : DecidableEq V]
  [partialOrder : PartialOrder V]
  root : V
  bot_le : ∀ v : V, root ≤ v
  down_chain : ∀ u₁ u₂ v : V, u₁ ≤ v → u₂ ≤ v → u₁ ≤ u₂ ∨ u₂ ≤ u₁
  color : V → Fin 4
  proper_coloring : ∀ u v : V, u < v → (∀ w : V, u ≤ w → w < v → w = u) → color u ≠ color v
See it in the graphDiscuss this resultChallenge it