simple_graph_reconfiguration_diam_le_three_halves_of_bipartite
Let G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree + 2, the diameter of the k-colouring reconfiguration graph of G with colours in Fin k is at most 3 * Fintype.card V / 2.
Statement
theorem simple_graph_reconfiguration_diam_le_three_halves_of_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) {k : ℕ} (hk : G.maxDegree + 2 ≤ k) : (simple_graph_reconfiguration_graph G k).diam ≤ 3 * Fintype.card V / 2
- Formalizes
- arXiv:2611.17022 Lemma 6 -- Large diameter for (Δ+2)-colouring reconfiguration
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_diam_le_of_forall_exists_walk_leIn any simple graph G on a type α, if for every pair of vertices u and v there exists a walk from u to v of length at most D, then the…
- simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartiteLet G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree +…
- simple_graph_reconfiguration_graphFor a simple graph G and a natural number k, the k-reconfiguration graph of G is the simple graph whose vertices are the proper…
Read back from the Lean
Let V be a finite type with decidable equality, and let G be a simple graph on V with decidable adjacency. Assume G is bipartite (hG : G.IsBipartite). Let k be a natural number such that G.maxDegree + 2 ≤ k. Then the diameter of the reconfiguration graph of proper k-colorings of G (the graph whose vertices are proper colorings c : V → Fin k and whose edges connect pairs of colorings differing at exactly one vertex of V) is at most 3 * Fintype.card V / 2 (using natural number division).
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
To bound the diameter of the k-colouring reconfiguration graph by ⌊3|V|/2⌋, the proof reduces the claim to showing that every pair of valid colourings is connected by a reconfiguration walk of length at most ⌊3|V|/2⌋. It then concludes immediately by invoking an existing result that constructs such a walk for any bipartite graph when k ≥ Δ(G) + 2.
The diameter of the k-colouring reconfiguration graph of G is at most ⌊3|V|/2⌋.
The lemma `simple_graph_diam_le_of_forall_exists_walk_le` reduces bounding the diameter of a graph by D to proving that any two vertices are connected by a walk of length at most D. Here, for any two k-colourings, `simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite` provides a reconfiguration walk of length at most ⌊3|V|/2⌋ using the bipartite hypothesis (hG) and the colour bound k ≥ Δ(G) + 2 (hk). Applying the diameter reduction to this walk bound completes the proof.
uses
simple_graph_diam_le_of_forall_exists_walk_le,simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite(simple_graph_reconfiguration_graph G k).diam ≤ 3 * Fintype.card V / 2 := simple_graph_diam_le_of_forall_exists_walk_le _ _ (simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite G hG hk)
simple_graph_diam_le_of_forall_exists_walk_le- A simple graph has diameter at most D if every pair of vertices is connected by a walk of length at most D.
simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite- In a finite bipartite simple graph G with maximum degree Δ(G) and k ≥ Δ(G) + 2, every pair of valid k-colourings is connected in the reconfiguration graph by a walk of length at most ⌊3|V|/2⌋.
- In Lean, natural number division `3 * Fintype.card V / 2` truncates towards zero, representing the floor $\lfloor 3|V|/2 \rfloor$.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Upper bound of ⌊3n/2⌋ on the recoloring diameter of a bipartite graph with k ≥ Δ(G) + 2 colours. -/theorem simple_graph_reconfiguration_diam_le_three_halves_of_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) {k : ℕ} (hk : G.maxDegree + 2 ≤ k) : (simple_graph_reconfiguration_graph G k).diam ≤ 3 * Fintype.card V / 2 := simple_graph_diam_le_of_forall_exists_walk_le _ _ (simple_graph_reconfiguration_exists_walk_le_three_halves_of_bipartite G hG hk)