AFTD Auto-Formalizing Theoretical Domains

maxcut_one_sum_indecomposable_delete_preconnected

theoremverified

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
Used by 2

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.

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

    lines 9–14

      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
  2. 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}.

    lines 15–20

      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)
  3. 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}ᶜ.

    lines 21–29

    uses mem_filter, mem_univ, true_and, SimpleGraph.Reachable.refl

      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])
  4. 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.

    lines 30–35

      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]
  5. 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.

    lines 36–52

    uses mem_filter, mem_univ, SimpleGraph.Adj.reachable

      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)
  6. 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.

    lines 53–63

    uses mem_univ

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

    line 64

      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.

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

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