ten_vertex_exchange_six_connected
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
- ten_vertex_exchange_graphThe simple graph built from the explicit ten-vertex edge set.
- ten_vertex_exchange_edgesThe 35 unordered edges of the explicit ten-vertex witness.
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- Arena.Reachable.transReachability is transitive.
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.
Adjacency is decidable automation
By unfolding the definition.
instance (u v : Fin 10) : Decidable (tv_adj u v) := by unfold tv_adj; infer_instance
Adjacency relation equivalence automation
By simp.
uses
tv_adj,ten_vertex_exchange_graph,SimpleGraph.fromEdgeSet_adjsimp [tv_adj, ten_vertex_exchange_graph, SimpleGraph.fromEdgeSet_adj]Minimum degree is 6 automation
By finite exhaustion.
decideNo four cycle complement automation
By finite exhaustion.
decideEvery vertex has a surviving neighbor
Because degree is at least 6 and at most 5 vertices removed.
uses
tv_min_degree,Finset.card_le_card,Finset.not_subset.mp,Finset.mem_filter.mplet 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⟩
At least one vertex survives
Because at most 5 of 10 vertices removed.
uses
Finset.card_le_card,Finset.card_univ,Fintype.card_fin,Finset.not_subset.mphave 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⟩
Main theorem
Main proof.
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
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 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⟩⟩