simple_graph_clique_blowup_edist
In the clique blow-up H of G, two vertices x ∈ Q_i and y ∈ Q_j with i ≠ j are at the same distance in H as v_i and v_j in G (including distance ∞ when disconnected).
Statement
theorem simple_graph_clique_blowup_edist {V : Type*} (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) (p q : Σ i, Fin (a i)) (hpq : p.1 ≠ q.1) : (simple_graph_clique_blowup G a).edist p q = G.edist p.1 q.1
- Source
- Claim 1 in the proof of arXiv:2610.09300 (On graphs whose powers are well-covered), Theorem 1.6; serves forall_power_well_covered_iff_clique_blowup.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_clique_blowupThe clique blow-up H = G[K_{a_1}, …, K_{a_n}]: each vertex v_i of G is replaced by a clique Q_i on a_i vertices, and distinct vertices x ∈…
- Used by 1
- simple_graph_power_well_covered_iff_clique_blowupFor every d ≥ 1 and positive integers a_i, G^d is well-covered iff H^d is well-covered, where H = G[K_{a_1}, …, K_{a_n}].
The proof, explained
To show that two vertices in different fibers have the same distance in the clique blow-up as their base vertices in G, the proof establishes mutual inequalities via antisymmetry. For the forward inequality, any shortest walk in G has length at least 1 (since the base vertices are distinct) and lifts edge-by-edge to a walk of the same length in the blow-up, using the assumption that all fibers are nonempty. For the reverse inequality, any walk in the blow-up projects to a walk in G of length at most that of the original walk, contracting internal clique edges to length zero and preserving edges between different fibers. Both inequalities extend naturally to the disconnected case where distances are infinite.
The empty walk in the clique blow-up projects to the empty walk in G.
By induction on the walk w in the blow-up, the base case of an empty walk (nil) between vertices in the same fiber projects to the empty walk in G (SimpleGraph.Walk.nil), which trivially has length 0 ≤ 0.
uses
SimpleGraph.Walk.nil,le_rflinduction w with | nil => exact ⟨SimpleGraph.Walk.nil, le_rfl⟩
Any walk in the clique blow-up projects to a walk in G of length at most that of the original walk.
In the inductive step for an edge (x, y) followed by a walk w from y to z, the induction hypothesis provides a projected walk w' in G from y.1 to z.1 with |w'| ≤ |w|. By definition of the blow-up, the edge (x, y) is either internal to a fiber (x.1 = y.1) or connects adjacent fibers (G.Adj x.1 y.1). If internal, w' already connects x.1 to z.1 (via w'.copy), giving a walk of length |w'| ≤ |w| + 1. If between adjacent fibers, prepending this edge to w' via SimpleGraph.Walk.cons yields a walk of length |w'| + 1 ≤ |w| + 1.
uses
SimpleGraph.Walk.length_cons,SimpleGraph.Walk.length_copy,SimpleGraph.Walk.cons| @cons x y z h w ih => obtain ⟨w', hw'⟩ := ih rw [SimpleGraph.Walk.length_cons] have h' : (x.1 = y.1 ∧ x ≠ y) ∨ G.Adj x.1 y.1 := h rcases h' with ⟨hxy, -⟩ | h' · exact ⟨w'.copy hxy.symm rfl, by rw [SimpleGraph.Walk.length_copy]; omega⟩ · exact ⟨SimpleGraph.Walk.cons h' w', by rw [SimpleGraph.Walk.length_cons]; omega⟩A walk of length at least 1 cannot be empty.
To show that any walk of length at least 1 in G lifts to the blow-up, we induct on the walk w. The base case of an empty walk is impossible since its length is 0, which contradicts the hypothesis 1 ≤ |w|.
induction w with | nil => intro p q _ _ h; simp at h
A single-edge walk in G lifts to an edge between corresponding fibers in the blow-up.
In the inductive step for a walk starting with edge x ~ y, if the remaining walk w has length 0, then y = z. Since x is adjacent to y in G, any vertex p over x is adjacent in the blow-up to any vertex q over z. The single-edge walk from p to q in the blow-up has length 1, which is at most the length of the original walk.
uses
SimpleGraph.Walk.eq_of_length_eq_zero,SimpleGraph.Walk.cons,SimpleGraph.Walk.nil| @cons x y z h w ih => intro p q hp hq _ by_cases hw : w.length = 0 · have hyz : y = z := SimpleGraph.Walk.eq_of_length_eq_zero hw have hadj : (simple_graph_clique_blowup G a).Adj p q := Or.inr (by rw [hp, hq, ← hyz]; exact h) refine ⟨SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil, ?_⟩ simpA walk of length at least 2 in G lifts inductively through a chosen vertex in the intermediate fiber.
If the remaining walk w has nonzero length, then |w| ≥ 1. Since the fiber over y is nonempty (0 < a(y)), we choose a canonical representative vertex ⟨y, 0⟩ in that fiber. Applying the induction hypothesis to this vertex and q yields a lifted walk w' of length |w'| ≤ |w|. Prepending the blow-up edge between p and ⟨y, 0⟩ produces a walk from p to q of length |w'| + 1 ≤ |w| + 1.
uses
SimpleGraph.Walk.cons,SimpleGraph.Walk.length_cons· obtain ⟨w', hw'⟩ := ih ⟨y, ⟨0, ha y⟩⟩ q rfl hq (Nat.one_le_iff_ne_zero.2 hw) have hadj : (simple_graph_clique_blowup G a).Adj p ⟨y, ⟨0, ha y⟩⟩ := Or.inr (by rw [hp]; exact h) refine ⟨SimpleGraph.Walk.cons hadj w', ?_⟩ simp only [SimpleGraph.Walk.length_cons]; omega
Equality of extended distances reduces to mutual inequalities.
We apply the antisymmetry of the partial order on extended natural numbers (le_antisymm), reducing the equality of distances to proving that the blow-up distance is bounded by the graph distance, and conversely.
uses
le_antisymmapply le_antisymmThe blow-up distance is bounded by the graph distance when the base vertices are disconnected.
We case split on whether G.edist p.1 q.1 = ⊤. If the distance in G is ⊤ (disconnected), the inequality edist_H(p, q) ≤ ⊤ holds trivially by le_top.
uses
le_top· by_cases htop : G.edist p.1 q.1 = ⊤ · rw [htop]; exact le_top
When the base vertices are connected, the blow-up distance is bounded above by the graph distance.
When G.edist p.1 q.1 ≠ ⊤, there exists a shortest walk w in G between p.1 and q.1 whose length equals the distance (SimpleGraph.exists_walk_of_edist_ne_top). Because p.1 ≠ q.1, this walk has length at least 1. By simple_graph_clique_blowup_walk_lift, w lifts to a walk w' from p to q in the blow-up with |w'| ≤ |w|. Since the blow-up distance is bounded by the length of any walk (SimpleGraph.edist_le), we obtain edist_H(p, q) ≤ |w'| ≤ |w| = edist_G(p.1, q.1).
uses
SimpleGraph.exists_walk_of_edist_ne_top,SimpleGraph.Walk.eq_of_length_eq_zero,simple_graph_clique_blowup_walk_lift,SimpleGraph.edist_leobtain ⟨w, hw⟩ := SimpleGraph.exists_walk_of_edist_ne_top htop have h1 : 1 ≤ w.length := by by_contra h0 exact hpq (SimpleGraph.Walk.eq_of_length_eq_zero (p := w) (by omega)) obtain ⟨w', hw'⟩ := simple_graph_clique_blowup_walk_lift G a ha w p q rfl rfl h1 calc (simple_graph_clique_blowup G a).edist p q ≤ w'.length := SimpleGraph.edist_le w' _ ≤ w.length := by exact_mod_cast hw' _ = G.edist p.1 q.1 := hw
The graph distance is bounded by the blow-up distance when the fiber vertices are disconnected.
Similarly, we case split on whether the distance between p and q in the blow-up is ⊤. If so, the inequality edist_G(p.1, q.1) ≤ ⊤ holds trivially by le_top.
uses
le_top· by_cases htop : (simple_graph_clique_blowup G a).edist p q = ⊤ · rw [htop]; exact le_top
When the fiber vertices are connected, the graph distance is bounded above by the blow-up distance.
When the blow-up distance is finite, there exists a walk w between p and q realizing that distance. By simple_graph_clique_blowup_walk_proj, w projects to a walk w' in G between p.1 and q.1 of length |w'| ≤ |w|. By SimpleGraph.edist_le, edist_G(p.1, q.1) ≤ |w'| ≤ |w| = edist_H(p, q), completing the proof.
uses
SimpleGraph.exists_walk_of_edist_ne_top,simple_graph_clique_blowup_walk_proj,SimpleGraph.edist_leobtain ⟨w, hw⟩ := SimpleGraph.exists_walk_of_edist_ne_top htop obtain ⟨w', hw'⟩ := simple_graph_clique_blowup_walk_proj G a w calc G.edist p.1 q.1 ≤ w'.length := SimpleGraph.edist_le w' _ ≤ w.length := by exact_mod_cast hw' _ = _ := hw
SimpleGraph.Walk.nil- The empty walk from a vertex to itself, having length 0.
le_rfl- Reflexivity of a preorder: every element is less than or equal to itself (a ≤ a).
SimpleGraph.Walk.length_cons- Prepending an edge to a walk increases its length by 1: |h :: p| = |p| + 1.
SimpleGraph.Walk.length_copy- Transporting the endpoints of a walk along propositional equalities preserves its length: |p.copy hu hv| = |p|.
SimpleGraph.Walk.cons- Extends a walk from v to w by prepending an edge u ~ v, producing a walk from u to w.
SimpleGraph.Walk.eq_of_length_eq_zero- A walk of length 0 starts and ends at the same vertex: if |p| = 0, then u = v.
le_antisymm- Antisymmetry of a partial order: if a ≤ b and b ≤ a, then a = b.
le_top- Every element in an order with a greatest element is bounded above by ⊤ (a ≤ ⊤).
SimpleGraph.exists_walk_of_edist_ne_top- If the extended distance between two vertices is finite, there exists a walk between them whose length equals that distance.
simple_graph_clique_blowup_walk_lift- When all fibers are nonempty, every walk of length at least 1 in G lifts to a walk between specified fiber vertices in the clique blow-up with length at most that of the original walk.
SimpleGraph.edist_le- The extended distance between two vertices is at most the length of any walk connecting them: edist u v ≤ |p|.
simple_graph_clique_blowup_walk_proj- Every walk in the clique blow-up projects to a walk between the corresponding base vertices in G with length at most that of the original walk.
- The requirement p.1 ≠ q.1 in simple_graph_clique_blowup_edist is essential: two distinct vertices in the same fiber have distance 1 in the blow-up (since each fiber is turned into a clique), whereas their base projection in G is a single vertex with self-distance 0.
- The projection of walks uses SimpleGraph.Walk.copy to adjust walk endpoints along propositional equalities without adding edges, contracting edges internal to a clique into stationary transitions in the base graph.
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 simple_graph_clique_blowup_walk_proj {V : Type*} (G : SimpleGraph V) (a : V → ℕ) {p q : Σ i, Fin (a i)} (w : (simple_graph_clique_blowup G a).Walk p q) : ∃ w' : G.Walk p.1 q.1, w'.length ≤ w.length := by induction w with | nil => exact ⟨SimpleGraph.Walk.nil, le_rfl⟩ | @cons x y z h w ih => obtain ⟨w', hw'⟩ := ih rw [SimpleGraph.Walk.length_cons] have h' : (x.1 = y.1 ∧ x ≠ y) ∨ G.Adj x.1 y.1 := h rcases h' with ⟨hxy, -⟩ | h' · exact ⟨w'.copy hxy.symm rfl, by rw [SimpleGraph.Walk.length_copy]; omega⟩ · exact ⟨SimpleGraph.Walk.cons h' w', by rw [SimpleGraph.Walk.length_cons]; omega⟩theorem simple_graph_clique_blowup_walk_lift {V : Type*} (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) {i j : V} (w : G.Walk i j) : ∀ p q : Σ i, Fin (a i), p.1 = i → q.1 = j → 1 ≤ w.length → ∃ w' : (simple_graph_clique_blowup G a).Walk p q, w'.length ≤ w.length := by induction w with | nil => intro p q _ _ h; simp at h | @cons x y z h w ih => intro p q hp hq _ by_cases hw : w.length = 0 · have hyz : y = z := SimpleGraph.Walk.eq_of_length_eq_zero hw have hadj : (simple_graph_clique_blowup G a).Adj p q := Or.inr (by rw [hp, hq, ← hyz]; exact h) refine ⟨SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil, ?_⟩ simp · obtain ⟨w', hw'⟩ := ih ⟨y, ⟨0, ha y⟩⟩ q rfl hq (Nat.one_le_iff_ne_zero.2 hw) have hadj : (simple_graph_clique_blowup G a).Adj p ⟨y, ⟨0, ha y⟩⟩ := Or.inr (by rw [hp]; exact h) refine ⟨SimpleGraph.Walk.cons hadj w', ?_⟩ simp only [SimpleGraph.Walk.length_cons]; omegatheorem simple_graph_clique_blowup_edist {V : Type*} (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) (p q : Σ i, Fin (a i)) (hpq : p.1 ≠ q.1) : (simple_graph_clique_blowup G a).edist p q = G.edist p.1 q.1 := by apply le_antisymm · by_cases htop : G.edist p.1 q.1 = ⊤ · rw [htop]; exact le_top obtain ⟨w, hw⟩ := SimpleGraph.exists_walk_of_edist_ne_top htop have h1 : 1 ≤ w.length := by by_contra h0 exact hpq (SimpleGraph.Walk.eq_of_length_eq_zero (p := w) (by omega)) obtain ⟨w', hw'⟩ := simple_graph_clique_blowup_walk_lift G a ha w p q rfl rfl h1 calc (simple_graph_clique_blowup G a).edist p q ≤ w'.length := SimpleGraph.edist_le w' _ ≤ w.length := by exact_mod_cast hw' _ = G.edist p.1 q.1 := hw · by_cases htop : (simple_graph_clique_blowup G a).edist p q = ⊤ · rw [htop]; exact le_top obtain ⟨w, hw⟩ := SimpleGraph.exists_walk_of_edist_ne_top htop obtain ⟨w', hw'⟩ := simple_graph_clique_blowup_walk_proj G a w calc G.edist p.1 q.1 ≤ w'.length := SimpleGraph.edist_le w' _ ≤ w.length := by exact_mod_cast hw' _ = _ := hw