AFTD Auto-Formalizing Theoretical Domains

simple_graph_reconfiguration_diam_le_three_halves_of_bipartite

theoremverifiedformalization

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

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.

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

    lines 7–8

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

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