op869_predecessor_colorable_iff
The graph built from predecessor sets is k-colorable exactly when the vertices admit k colors with different colors on each earlier-neighbor incidence.
Statement
theorem op869_predecessor_colorable_iff {n k : ℕ} (P : Fin n → Finset (Fin n)) :
(op869_graph_from_predecessors P).Colorable k ↔
∃ c : Fin n → Fin k, ∀ i j : Fin n, i < j → i ∈ P j → c i ≠ c j- Source
- arXiv:2610.41516, Sections 1 and 2; formal infrastructure for the adaptive online-coloring construction.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op869_graph_from_predecessorsThe simple graph on the ordered vertices Fin n whose edge from an earlier vertex a to a later vertex b exists exactly when a is in the…
The proof, explained
The equivalence is proved in two directions. For the forward direction, a valid $k$-coloring of the graph must give different colors to adjacent vertices, which immediately covers all pairs $i < j$ with $i \in P(j)$ by definition of the predecessor graph. For the reverse direction, any coloring separating such predecessor pairs is a proper graph coloring, because every edge between $i$ and $j$ corresponds to either $i < j$ with $i \in P(j)$ or $j < i$ with $j \in P(i)$, both forcing $c(i) \neq c(j)$ either directly or by symmetry of inequality.
Any proper $k$-coloring of the predecessor graph assigns distinct colors to every pair of vertices $i < j$ with $i \in P(j)$.
We split the if-and-only-if statement into two implications. In the forward direction, assuming the graph is $k$-colorable, we obtain a valid coloring $c : \text{Fin } n \to \text{Fin } k$. For any vertices $i < j$ with $i \in P(j)$, the definition of adjacency in the predecessor graph is satisfied via its first alternative (using `Or.inl`). Because $c$ is a valid graph coloring, adjacent vertices have distinct colors, giving $c(i) \neq c(j)$.
uses
Or.inlconstructor · rintro ⟨c⟩ refine ⟨c, ?_⟩ intro i j hij hmem exact c.valid (Or.inl ⟨hij, hmem⟩)
Conversely, any vertex coloring assigning distinct colors to predecessor pairs is a valid $k$-coloring of the predecessor graph.
Given a vertex coloring $c : \text{Fin } n \to \text{Fin } k$ satisfying the predecessor condition, we build a proper graph coloring using `SimpleGraph.Coloring.mk`. It remains to show that any adjacent vertices $i$ and $j$ receive distinct colors. By definition of the predecessor graph, adjacency means either $i < j$ with $i \in P(j)$, or $j < i$ with $j \in P(i)$. In the first case, the hypothesis directly gives $c(i) \neq c(j)$. In the second case, the hypothesis gives $c(j) \neq c(i)$, from which $c(i) \neq c(j)$ follows by the symmetry of inequality (`Ne.symm`).
uses
SimpleGraph.Coloring.mk,Ne.symm· rintro ⟨c, hc⟩ refine ⟨SimpleGraph.Coloring.mk c ?_⟩ intro i j hadj rcases hadj with ⟨hij, hmem⟩ | ⟨hji, hmem⟩ · exact hc i j hij hmem · exact Ne.symm (hc j i hji hmem)
Or.inl- Given a proof of $P$, constructs a proof of the disjunction $P \lor Q$.
SimpleGraph.Coloring.mk- Constructs a proper coloring of a graph from a vertex coloring function and a proof that adjacent vertices receive distinct colors.
Ne.symm- Inequality is symmetric: if $a \neq b$, then $b \neq a$.
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.
theorem op869_predecessor_colorable_iff {n k : ℕ} (P : Fin n → Finset (Fin n)) : (op869_graph_from_predecessors P).Colorable k ↔ ∃ c : Fin n → Fin k, ∀ i j : Fin n, i < j → i ∈ P j → c i ≠ c j := by constructor · rintro ⟨c⟩ refine ⟨c, ?_⟩ intro i j hij hmem exact c.valid (Or.inl ⟨hij, hmem⟩) · rintro ⟨c, hc⟩ refine ⟨SimpleGraph.Coloring.mk c ?_⟩ intro i j hadj rcases hadj with ⟨hij, hmem⟩ | ⟨hji, hmem⟩ · exact hc i j hij hmem · exact Ne.symm (hc j i hji hmem)