AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_six_connected

theoremverified

Deleting any at most five vertices leaves the ten-vertex witness graph connected.

Statement

theorem ten_vertex_exchange_six_connected : ∀ R : Finset (Fin 10), R.card ≤ 5 → (ten_vertex_exchange_graph.induce {v | v ∉ R}).Connected
Source
Explicit ten-vertex witness for simple_graph_stable_point_irreducible_forced_exchange_barrier_counterexample.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The ten-vertex exchange graph is 6-connected. Deleting at most 5 vertices leaves each surviving vertex with degree at least 1 in the induced subgraph, and if two components existed, choosing an edge in each would form an induced 2K2 whose complement would contain a C4, contradicting the graph's structure checked by finite exhaustion.

  1. Adjacency is decidable automation

    By unfolding the definition.

    line 5

    instance (u v : Fin 10) : Decidable (tv_adj u v) := by unfold tv_adj; infer_instance
  2. Adjacency relation equivalence automation

    By simp.

    line 7

    uses tv_adj, ten_vertex_exchange_graph, SimpleGraph.fromEdgeSet_adj

      simp [tv_adj, ten_vertex_exchange_graph, SimpleGraph.fromEdgeSet_adj]
  3. Minimum degree is 6 automation

    By finite exhaustion.

    line 12

      decide
  4. No four cycle complement automation

    By finite exhaustion.

    line 19

      decide
  5. Every vertex has a surviving neighbor

    Because degree is at least 6 and at most 5 vertices removed.

    lines 24–31

    uses tv_min_degree, Finset.card_le_card, Finset.not_subset.mp, Finset.mem_filter.mp

      let N := (Finset.univ : Finset (Fin 10)).filter (tv_adj u)
      have hN : 6 ≤ N.card := tv_min_degree u
      have hns : ¬ N ⊆ R := by
        intro h
        have := Finset.card_le_card h
        omega
      obtain ⟨v, hvN, hvR⟩ := Finset.not_subset.mp hns
      exact ⟨v, hvR, (Finset.mem_filter.mp hvN).2⟩
  6. At least one vertex survives

    Because at most 5 of 10 vertices removed.

    lines 34–40

    uses Finset.card_le_card, Finset.card_univ, Fintype.card_fin, Finset.not_subset.mp

      have h : ¬ (Finset.univ : Finset (Fin 10)) ⊆ R := by
        intro h
        have hc := Finset.card_le_card h
        simp only [Finset.card_univ, Fintype.card_fin] at hc
        omega
      obtain ⟨u, _, hu⟩ := Finset.not_subset.mp h
      exact ⟨u, hu⟩
  7. Main theorem

    Main proof.

    lines 43–79

      intro R hR
      let K := ten_vertex_exchange_graph.induce {v | v ∉ R}
      have hn : ∀ u : {v // v ∉ R}, ∃ v, K.Adj u v := by
        intro u
        obtain ⟨v, hv, huv⟩ := tv_neighbor_survives R hR u.val
        exact ⟨⟨v, hv⟩, (tv_adj_iff u.val v).mp huv⟩
      apply (SimpleGraph.connected_iff K).mpr
      constructor
      · intro a b
        by_contra hnot
        obtain ⟨x, hax⟩ := hn a
        obtain ⟨y, hby⟩ := hn b
        have cross {u v : {v // v ∉ R}} (hu : K.Reachable a u) (hv : K.Reachable b v) :
            u ≠ v ∧ ¬ K.Adj u v := by
          constructor
          · intro he
            subst v
            exact hnot (hu.trans hv.symm)
          · intro h
            exact hnot ((hu.trans h.reachable).trans hv.symm)
        have h1 := cross (SimpleGraph.Reachable.refl a) (SimpleGraph.Reachable.refl b)
        have h2 := cross hax.reachable (SimpleGraph.Reachable.refl b)
        have h3 := cross (SimpleGraph.Reachable.refl a) hby.reachable
        have h4 := cross hax.reachable hby.reachable
        have hnval {u v : {v // v ∉ R}} (h : u ≠ v) : u.val ≠ v.val := by
          intro he
          apply h
          exact Subtype.ext he
        have hnadj {u v : {v // v ∉ R}} (h : ¬ K.Adj u v) : ¬ tv_adj u.val v.val := by
          intro h'
          apply h
          exact (tv_adj_iff u.val v.val).mp h'
        exact tv_no_four_cycle_complement a.val x.val b.val y.val
          (hnval hax.ne) (hnval hby.ne) (hnval h1.1).symm (hnval h2.1).symm
          (hnval h3.1).symm (hnval h4.1).symm (hnadj h1.2) (hnadj h2.2) (hnadj h3.2) (hnadj h4.2)
      · obtain ⟨u, hu⟩ := tv_survivor R hR
        exact ⟨⟨u, hu⟩⟩
tv_min_degree
foo

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 scoped Sym2open SimpleGraphdef tv_adj (u v : Fin 10) : Prop := s(u,v) ∈ ten_vertex_exchange_edges ∧ u ≠ vinstance (u v : Fin 10) : Decidable (tv_adj u v) := by unfold tv_adj; infer_instancelemma tv_adj_iff (u v : Fin 10) : tv_adj u v ↔ ten_vertex_exchange_graph.Adj u v := by  simp [tv_adj, ten_vertex_exchange_graph, SimpleGraph.fromEdgeSet_adj]set_option maxRecDepth 8192 inset_option maxHeartbeats 3000000 inlemma tv_min_degree : ∀ u : Fin 10, 6 ≤ ((Finset.univ : Finset (Fin 10)).filter (tv_adj u)).card := by  decideset_option maxRecDepth 8192 inset_option maxHeartbeats 3000000 inlemma tv_no_four_cycle_complement : ∀ (a b c d : Fin 10),    a ≠ b → c ≠ d → c ≠ a → c ≠ b → d ≠ a → d ≠ b →    ¬ tv_adj a c → ¬ tv_adj b c → ¬ tv_adj a d → ¬ tv_adj b d → False := by  decidelemma tv_neighbor_survives (R : Finset (Fin 10)) (hR : R.card ≤ 5)    (u : Fin 10) : ∃ v, v ∉ R ∧ tv_adj u v := by  let N := (Finset.univ : Finset (Fin 10)).filter (tv_adj u)  have hN : 6 ≤ N.card := tv_min_degree u  have hns : ¬ N ⊆ R := by    intro h    have := Finset.card_le_card h    omega  obtain ⟨v, hvN, hvR⟩ := Finset.not_subset.mp hns  exact ⟨v, hvR, (Finset.mem_filter.mp hvN).2⟩lemma tv_survivor (R : Finset (Fin 10)) (hR : R.card ≤ 5) : ∃ u : Fin 10, u ∉ R := by  have h : ¬ (Finset.univ : Finset (Fin 10)) ⊆ R := by    intro h    have hc := Finset.card_le_card h    simp only [Finset.card_univ, Fintype.card_fin] at hc    omega  obtain ⟨u, _, hu⟩ := Finset.not_subset.mp h  exact ⟨u, hu⟩theorem ten_vertex_exchange_six_connected : ∀ R : Finset (Fin 10), R.card ≤ 5 → (ten_vertex_exchange_graph.induce {v | v ∉ R}).Connected := by  intro R hR  let K := ten_vertex_exchange_graph.induce {v | v ∉ R}  have hn : ∀ u : {v // v ∉ R}, ∃ v, K.Adj u v := by    intro u    obtain ⟨v, hv, huv⟩ := tv_neighbor_survives R hR u.val    exact ⟨⟨v, hv⟩, (tv_adj_iff u.val v).mp huv⟩  apply (SimpleGraph.connected_iff K).mpr  constructor  · intro a b    by_contra hnot    obtain ⟨x, hax⟩ := hn a    obtain ⟨y, hby⟩ := hn b    have cross {u v : {v // v ∉ R}} (hu : K.Reachable a u) (hv : K.Reachable b v) :        u ≠ v ∧ ¬ K.Adj u v := by      constructor      · intro he        subst v        exact hnot (hu.trans hv.symm)      · intro h        exact hnot ((hu.trans h.reachable).trans hv.symm)    have h1 := cross (SimpleGraph.Reachable.refl a) (SimpleGraph.Reachable.refl b)    have h2 := cross hax.reachable (SimpleGraph.Reachable.refl b)    have h3 := cross (SimpleGraph.Reachable.refl a) hby.reachable    have h4 := cross hax.reachable hby.reachable    have hnval {u v : {v // v ∉ R}} (h : u ≠ v) : u.val ≠ v.val := by      intro he      apply h      exact Subtype.ext he    have hnadj {u v : {v // v ∉ R}} (h : ¬ K.Adj u v) : ¬ tv_adj u.val v.val := by      intro h'      apply h      exact (tv_adj_iff u.val v.val).mp h'    exact tv_no_four_cycle_complement a.val x.val b.val y.val      (hnval hax.ne) (hnval hby.ne) (hnval h1.1).symm (hnval h2.1).symm      (hnval h3.1).symm (hnval h4.1).symm (hnadj h1.2) (hnadj h2.2) (hnadj h3.2) (hnadj h4.2)  · obtain ⟨u, hu⟩ := tv_survivor R hR    exact ⟨⟨u, hu⟩⟩
See it in the graphDiscuss this resultChallenge it