maxcut_one_sum_indecomposable_delete_preconnected
If a finite graph has no nontrivial separation into two induced pieces meeting at one vertex, then after deleting any vertex every two remaining vertices are connected by a walk. The empty and singleton deletions are included.
Statement
theorem maxcut_one_sum_indecomposable_delete_preconnected {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hind : ∀ (A B : Finset V) (o : V), A ∪ B = Finset.univ → A ∩ B = {o} → (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) → A = Finset.univ ∨ B = Finset.univ) : ∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected
- Source
- Structural reduction for OP-85, the unweighted Max-k-Cut strong-equilibrium existence problem in arXiv:2610.04948, Section 4.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Arena.Reachable.transReachability is transitive.
- Used by 2
- maxcut_strong_equilibrium_reduce_vertex_deletionsFix k. If every finite graph whose every vertex deletion is preconnected has a strong k-color equilibrium, then every finite graph has a…
- maxcut_strong_equilibrium_reduce_connected_coreFix k. If every finite graph of minimum degree at least k whose every vertex deletion is preconnected has a strong k-color equilibrium,…
The proof, explained
The proof proceeds by contradiction. If deleting a vertex o leaves two vertices u and v that cannot reach each other in G \ {o}, let C be the connected component of u in G \ {o}. Adjoining o to C and to its complement yields two subsets A = C ∪ {o} and B = (V \ C) ∪ {o} that cover V, meet only at {o}, and have no edge between A \ B and B \ A. By the 1-sum indecomposability hypothesis, either A or B must be the whole vertex set, but this contradicts the fact that v ∉ A and u ∉ B.
Assume for contradiction that deleting some vertex o disconnects the graph, leaving two vertices u and v that cannot reach each other.
We argue by contradiction. The goal is that for every vertex o, the induced subgraph on {o}ᶜ is preconnected, meaning every pair of vertices in it is reachable by a walk. Negating this yields a vertex o and two vertices u, v in {o}ᶜ such that u cannot reach v in G \ {o}.
classical intro o by_contra hf change ¬ ∀ u v, (G.induce ({o}ᶜ : Set V)).Reachable u v at hf push Not at hf obtain ⟨u, v, huv⟩ := hf
Construct subsets A and B by adjoining the cut vertex o to the connected component C of u in G \ {o} and to its complement.
Let D = {o}ᶜ be the domain of the vertex-deleted subgraph H = G[D]. We define C to be the finset of all vertices in D reachable from u in H (the connected component of u). We then form A = C ∪ {o} and B = (V \ C) ∪ {o}.
let D : Set V := {o}ᶜ let H := G.induce D let P : V → Prop := fun x => ∃ hx : x ∈ D, H.Reachable u ⟨x, hx⟩ let C : Finset V := Finset.univ.filter P let A : Finset V := insert o C let B : Finset V := insert o (Finset.univ \ C)
The basepoint o ∉ C, u ∈ C, v ∉ C, and v ≠ o.
Because o ∉ D, o cannot satisfy the reachability predicate P, so o ∉ C. The vertex u is in D and reaches itself by reflexivity (SimpleGraph.Reachable.refl), hence u ∈ C. If v were in C, u would reach v, contradicting our choice of u and v, so v ∉ C. Finally, v ≠ o because v is a vertex of {o}ᶜ.
uses
mem_filter,mem_univ,true_and,SimpleGraph.Reachable.reflhave hoC : o ∉ C := by simp [C, P, D] have huC : u.1 ∈ C := by simp only [C, mem_filter, mem_univ, true_and] exact ⟨u.2, SimpleGraph.Reachable.refl u⟩ have hvC : v.1 ∉ C := by simp only [C, mem_filter, mem_univ, true_and] rintro ⟨hv, hr⟩ exact huv hr have hvne : v.1 ≠ o := fun h => v.2 (by simp [h])
A ∪ B = V and A ∩ B = {o}. automation
Since C and V \ C partition V, adjoining o to both sets covers all of V. For the intersection, o belongs to both A and B, while any other vertex x belongs to exactly one of C and V \ C, so A ∩ B = {o}. In Lean, extensionality and simplification over the definitions of A and B discharge both set identities.
have hcover : A ∪ B = Finset.univ := by ext x simp [A, B] have hinter : A ∩ B = {o} := by ext x by_cases hx : x = o <;> simp [A, B, hx, hoC]
There is no edge in G between A \ B and B \ A.
Suppose for contradiction that G has an edge between x ∈ A \ B and y ∈ B \ A. Since x ∉ B, x must be in C. Since y ∉ A, y cannot be o (so y ∈ D) and y ∉ C. Because x ∈ C, u can reach x in H. Because x and y are adjacent in G and both lie in D, they are adjacent in H, so x reaches y (SimpleGraph.Adj.reachable). By transitivity of reachability in H, u can reach y, placing y in C, which contradicts y ∉ C.
uses
mem_filter,mem_univ,SimpleGraph.Adj.reachablehave hsep : ∀ x ∈ A, x ∉ B → ∀ y ∈ B, y ∉ A → ¬ G.Adj x y := by intro x hx hxB y hy hyA hxy have hxC : x ∈ C := by by_contra hh exact hxB (by simp [B, hh]) have hyC : y ∉ C := by intro hh exact hyA (by simp [A, hh]) have hyD : y ∈ D := by have : y ≠ o := by intro h; subst y; exact hyA (by simp [A]) simpa [D] using this have ⟨hxD, hr⟩ : P x := (mem_filter.mp hxC).2 apply hyC apply mem_filter.mpr refine ⟨mem_univ _, ⟨hyD, ?_⟩⟩ exact hr.trans (SimpleGraph.Adj.reachable hxy)
Neither A nor B is the entire vertex set V.
If A were univ, then v would belong to A, meaning v = o or v ∈ C, both of which are false. If B were univ, then u would belong to B, meaning u = o or u ∉ C, both of which are false. Hence A ≠ univ and B ≠ univ.
uses
mem_univhave hAn : A ≠ Finset.univ := by intro h have : v.1 ∈ A := by rw [h]; exact mem_univ _ have : v.1 = o ∨ v.1 ∈ C := by simpa [A] using this exact this.elim hvne hvC have hBn : B ≠ Finset.univ := by intro h have : u.1 ∈ B := by rw [h]; exact mem_univ _ have hune : u.1 ≠ o := fun h => u.2 (by simp [h]) have : u.1 = o ∨ u.1 ∉ C := by simpa [B] using this exact this.elim hune (fun hh => hh huC)
Contradiction with the 1-sum indecomposability hypothesis hind.
Applying the hypothesis hind to A, B, and o with the covering, intersection, and separation properties implies that A = univ or B = univ. Because both were proved to be proper subsets, this is a contradiction.
exact (hind A B o hcover hinter hsep).elim hAn hBn
mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction True ∧ p is logically equivalent to p.
SimpleGraph.Reachable.refl- In any graph, every vertex can reach itself via a trivial walk.
SimpleGraph.Adj.reachable- In any graph, adjacent vertices are reachable from one another via a walk of length 1.
- In Lean's SimpleGraph library, the induced subgraph on {o}ᶜ has vertices of subtype ↑{o}ᶜ. Vertices u and v in this subgraph are represented as pairs ⟨u.1, u.2⟩, where u.1 is the underlying vertex in V and u.2 is the proof that u.1 ≠ o.
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.
open Finsettheorem maxcut_one_sum_indecomposable_delete_preconnected {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hind : ∀ (A B : Finset V) (o : V), A ∪ B = Finset.univ → A ∩ B = {o} → (∀ v ∈ A, v ∉ B → ∀ w ∈ B, w ∉ A → ¬ G.Adj v w) → A = Finset.univ ∨ B = Finset.univ) : ∀ o : V, (G.induce ({o}ᶜ : Set V)).Preconnected := by classical intro o by_contra hf change ¬ ∀ u v, (G.induce ({o}ᶜ : Set V)).Reachable u v at hf push Not at hf obtain ⟨u, v, huv⟩ := hf let D : Set V := {o}ᶜ let H := G.induce D let P : V → Prop := fun x => ∃ hx : x ∈ D, H.Reachable u ⟨x, hx⟩ let C : Finset V := Finset.univ.filter P let A : Finset V := insert o C let B : Finset V := insert o (Finset.univ \ C) have hoC : o ∉ C := by simp [C, P, D] have huC : u.1 ∈ C := by simp only [C, mem_filter, mem_univ, true_and] exact ⟨u.2, SimpleGraph.Reachable.refl u⟩ have hvC : v.1 ∉ C := by simp only [C, mem_filter, mem_univ, true_and] rintro ⟨hv, hr⟩ exact huv hr have hvne : v.1 ≠ o := fun h => v.2 (by simp [h]) have hcover : A ∪ B = Finset.univ := by ext x simp [A, B] have hinter : A ∩ B = {o} := by ext x by_cases hx : x = o <;> simp [A, B, hx, hoC] have hsep : ∀ x ∈ A, x ∉ B → ∀ y ∈ B, y ∉ A → ¬ G.Adj x y := by intro x hx hxB y hy hyA hxy have hxC : x ∈ C := by by_contra hh exact hxB (by simp [B, hh]) have hyC : y ∉ C := by intro hh exact hyA (by simp [A, hh]) have hyD : y ∈ D := by have : y ≠ o := by intro h; subst y; exact hyA (by simp [A]) simpa [D] using this have ⟨hxD, hr⟩ : P x := (mem_filter.mp hxC).2 apply hyC apply mem_filter.mpr refine ⟨mem_univ _, ⟨hyD, ?_⟩⟩ exact hr.trans (SimpleGraph.Adj.reachable hxy) have hAn : A ≠ Finset.univ := by intro h have : v.1 ∈ A := by rw [h]; exact mem_univ _ have : v.1 = o ∨ v.1 ∈ C := by simpa [A] using this exact this.elim hvne hvC have hBn : B ≠ Finset.univ := by intro h have : u.1 ∈ B := by rw [h]; exact mem_univ _ have hune : u.1 ≠ o := fun h => u.2 (by simp [h]) have : u.1 = o ∨ u.1 ∉ C := by simpa [B] using this exact this.elim hune (fun hh => hh huC) exact (hind A B o hcover hinter hsep).elim hAn hBn