ten_vertex_exchange_edge_avoidable
For each of the 35 edges, a ten-triangle packing avoids that edge.
Statement
theorem ten_vertex_exchange_edge_avoidable : ∀ e ∈ ten_vertex_exchange_graph.edgeSet, ∃ R : Finset (Finset (Sym2 (Fin 10))), R ⊆ simple_graph_triangle_edge_family ten_vertex_exchange_graph ∧ R.card = 10 ∧ (R : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ e ∉ R.biUnion id- 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 9
- ten_vertex_exchange_graphThe simple graph built from the explicit ten-vertex edge set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- ten_vertex_exchange_edge_setThe witness graph has exactly the 35 listed edges.
- ten_vertex_exchange_packing_qThe selected good ten-triangle packing.
- ten_vertex_exchange_familyThe explicit list of 52 triangle edge sets for the ten-vertex witness.
- ten_vertex_exchange_triangleThe three edges of a triangle on specified vertices.
- ten_vertex_exchange_edgesThe 35 unordered edges of the explicit ten-vertex witness.
- ten_vertex_exchange_packing_pThe selected ten-triangle packing in the local exchange trap.
The proof, explained
To prove that each of the 35 edges in the 10-vertex exchange graph is avoided by a packing of 10 pairwise disjoint triangles, the proof provides an explicit list of 11 candidate packings. An auxiliary lemma verifies by automated computation that each candidate is a valid 10-triangle packing. A second lemma exhaustively checks by computation that every edge is avoided by at least one of these 11 packings. For any given edge in the graph, the main theorem selects the avoiding packing from the list and concludes that it satisfies all conditions.
Every candidate packing in `ten_vertex_exchange_edge_avoidable_packings` is a valid 10-triangle packing in `ten_vertex_exchange_family`. automation
Assuming `R` belongs to `ten_vertex_exchange_edge_avoidable_packings`, rewriting list membership produces an 11-way disjunction corresponding to the 11 candidate packings. Performing a case split yields 11 subgoals, each verified by the decision procedure `decide`, which computationally confirms that the packing is a subset of `ten_vertex_exchange_family`, has cardinality 10, and consists of pairwise disjoint triangles.
uses
ten_vertex_exchange_edge_avoidable_packings,List.mem_cons,List.not_mem_nil,or_falseintro R hR simp only [ten_vertex_exchange_edge_avoidable_packings, List.mem_cons, List.not_mem_nil, or_false] at hR rcases hR with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decide
For every edge $e \in \text{ten\_vertex\_exchange\_edges}$, there exists a candidate packing avoiding $e$. automation
Because the graph has 35 edges and there are 11 candidate packings, the assertion that every edge is avoided by at least one packing in the list is a finite decidable property. The `decide` tactic checks this claim by exhaustive computation.
decideAny edge $e$ in the edge set of the graph belongs to the finite set `ten_vertex_exchange_edges`.
Let $e$ be an arbitrary edge in the graph's edge set. By `ten_vertex_exchange_edge_set.1.symm`, the graph's edge set equals the set coercion of `ten_vertex_exchange_edges`. Rewriting with this equality and applying `Finset.mem_coe.mp` establishes that $e$ belongs to the finite set `ten_vertex_exchange_edges`.
uses
ten_vertex_exchange_edge_set.1.symm,Finset.mem_coe.mpintro e he have he_edges : e ∈ ten_vertex_exchange_edges := by have h := ten_vertex_exchange_edge_set.1.symm have he' : e ∈ (↑ten_vertex_exchange_edges : Set (Sym2 (Fin 10))) := h ▸ he exact Finset.mem_coe.mp he'
There exists a candidate packing $R$ avoiding $e$ that is a valid packing of 10 pairwise disjoint triangles in `ten_vertex_exchange_family`.
Applying `ten_vertex_exchange_edge_avoidable_check` to $e \in \text{ten\_vertex\_exchange\_edges}$ provides a packing $R$ in the candidate list avoiding $e$. Applying `ten_vertex_exchange_edge_avoidable_packings_valid` to $R$ then extracts the facts that $R \subseteq \text{ten\_vertex\_exchange\_family}$, $|R| = 10$, and the triangles in $R$ are pairwise disjoint.
uses
ten_vertex_exchange_edge_avoidable_check,ten_vertex_exchange_edge_avoidable_packings_validobtain ⟨R, hR, heR⟩ := ten_vertex_exchange_edge_avoidable_check e he_edges obtain ⟨hsub, hcard, hdisj⟩ := ten_vertex_exchange_edge_avoidable_packings_valid R hR
The packing $R$ witnesses the theorem for $e$.
We provide $R$ as the witness for the existential claim. The size, pairwise disjointness, and avoidance of $e$ are already known. The inclusion into the triangle family of `ten_vertex_exchange_graph` follows by rewriting with `ten_vertex_exchange_family_eq`, which equates that family with `ten_vertex_exchange_family`.
uses
ten_vertex_exchange_family_eqrefine ⟨R, ?_, hcard, hdisj, heR⟩ rw [ten_vertex_exchange_family_eq] exact hsub
ten_vertex_exchange_edge_avoidable_packings- The definition of the list of 11 candidate triangle packings for the 10-vertex exchange graph.
List.mem_cons- An element belongs to a non-empty list `b :: l` if and only if it equals the head `b` or belongs to the tail `l`.
List.not_mem_nil- No element belongs to the empty list `[]`.
or_false- For any proposition `p`, the disjunction `p ∨ False` is logically equivalent to `p`.
ten_vertex_exchange_edge_set.1.symm- The edge set of `ten_vertex_exchange_graph` equals the set coercion of the finite edge set `ten_vertex_exchange_edges`.
Finset.mem_coe.mp- If an element belongs to the set coercion of a finite set, it belongs to the finite set.
ten_vertex_exchange_edge_avoidable_check- For every edge in `ten_vertex_exchange_edges`, there exists a packing in `ten_vertex_exchange_edge_avoidable_packings` that avoids it.
ten_vertex_exchange_edge_avoidable_packings_valid- Every packing in `ten_vertex_exchange_edge_avoidable_packings` is a subset of `ten_vertex_exchange_family`, has cardinality 10, and consists of pairwise disjoint triangles.
ten_vertex_exchange_family_eq- The triangle edge family of `ten_vertex_exchange_graph` is equal to the explicit family `ten_vertex_exchange_family`.
- The validity of each of the 11 candidate packings (that they contain 10 pairwise disjoint triangles belonging to the triangle family) is verified by automated decision procedures (`decide`) across 11 case splits.
- The existence of a candidate packing avoiding each of the 35 edges is verified by automated exhaustive search (`decide`).
- Converting membership from the graph edge set `ten_vertex_exchange_graph.edgeSet` to the finite set `ten_vertex_exchange_edges` is a formal coercion step between `Set` and `Finset`.
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.
def ten_vertex_exchange_edge_avoidable_packings : List (Finset (Finset (Sym2 (Fin 10)))) := [ ten_vertex_exchange_packing_q, {ten_vertex_exchange_triangle 0 1 3, ten_vertex_exchange_triangle 0 2 8, ten_vertex_exchange_triangle 0 6 7, ten_vertex_exchange_triangle 1 2 7, ten_vertex_exchange_triangle 4 6 8, ten_vertex_exchange_triangle 3 4 7, ten_vertex_exchange_triangle 1 4 5, ten_vertex_exchange_triangle 5 8 9, ten_vertex_exchange_triangle 2 3 9, ten_vertex_exchange_triangle 3 5 6}, {ten_vertex_exchange_triangle 0 1 3, ten_vertex_exchange_triangle 0 2 9, ten_vertex_exchange_triangle 0 7 8, ten_vertex_exchange_triangle 3 6 9, ten_vertex_exchange_triangle 4 6 8, ten_vertex_exchange_triangle 5 8 9, ten_vertex_exchange_triangle 2 3 7, ten_vertex_exchange_triangle 3 4 5, ten_vertex_exchange_triangle 1 2 5, ten_vertex_exchange_triangle 1 4 7}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 2 8 9, ten_vertex_exchange_triangle 0 2 3, ten_vertex_exchange_triangle 0 6 9, ten_vertex_exchange_triangle 3 5 9, ten_vertex_exchange_triangle 1 2 5, ten_vertex_exchange_triangle 3 4 6, ten_vertex_exchange_triangle 2 4 7, ten_vertex_exchange_triangle 6 7 8, ten_vertex_exchange_triangle 4 5 8}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 2 8 9, ten_vertex_exchange_triangle 0 3 9, ten_vertex_exchange_triangle 0 6 8, ten_vertex_exchange_triangle 5 6 9, ten_vertex_exchange_triangle 4 6 7, ten_vertex_exchange_triangle 4 5 8, ten_vertex_exchange_triangle 2 3 7, ten_vertex_exchange_triangle 1 2 4, ten_vertex_exchange_triangle 1 3 5}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 0 2 8, ten_vertex_exchange_triangle 0 3 9, ten_vertex_exchange_triangle 2 5 9, ten_vertex_exchange_triangle 6 8 9, ten_vertex_exchange_triangle 4 5 6, ten_vertex_exchange_triangle 3 6 7, ten_vertex_exchange_triangle 4 7 8, ten_vertex_exchange_triangle 1 3 5, ten_vertex_exchange_triangle 1 2 4}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 0 2 8, ten_vertex_exchange_triangle 0 3 9, ten_vertex_exchange_triangle 2 5 9, ten_vertex_exchange_triangle 6 8 9, ten_vertex_exchange_triangle 4 5 8, ten_vertex_exchange_triangle 3 5 6, ten_vertex_exchange_triangle 4 6 7, ten_vertex_exchange_triangle 2 3 7, ten_vertex_exchange_triangle 1 3 4}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 0 2 8, ten_vertex_exchange_triangle 0 3 9, ten_vertex_exchange_triangle 1 2 5, ten_vertex_exchange_triangle 4 5 8, ten_vertex_exchange_triangle 6 8 9, ten_vertex_exchange_triangle 3 5 6, ten_vertex_exchange_triangle 4 6 7, ten_vertex_exchange_triangle 2 3 7, ten_vertex_exchange_triangle 1 3 4}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 0 2 8, ten_vertex_exchange_triangle 0 6 9, ten_vertex_exchange_triangle 5 8 9, ten_vertex_exchange_triangle 2 3 9, ten_vertex_exchange_triangle 1 2 5, ten_vertex_exchange_triangle 1 3 4, ten_vertex_exchange_triangle 3 6 7, ten_vertex_exchange_triangle 4 5 6, ten_vertex_exchange_triangle 4 7 8}, {ten_vertex_exchange_triangle 0 1 7, ten_vertex_exchange_triangle 0 2 9, ten_vertex_exchange_triangle 3 4 6, ten_vertex_exchange_triangle 0 6 8, ten_vertex_exchange_triangle 5 6 9, ten_vertex_exchange_triangle 4 7 8, ten_vertex_exchange_triangle 2 3 7, ten_vertex_exchange_triangle 1 3 5, ten_vertex_exchange_triangle 1 2 4, ten_vertex_exchange_triangle 2 5 8}, ten_vertex_exchange_packing_p]lemma ten_vertex_exchange_edge_avoidable_packings_valid : ∀ R ∈ ten_vertex_exchange_edge_avoidable_packings, R ⊆ ten_vertex_exchange_family ∧ R.card = 10 ∧ (R : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint := by intro R hR simp only [ten_vertex_exchange_edge_avoidable_packings, List.mem_cons, List.not_mem_nil, or_false] at hR rcases hR with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> decidelemma ten_vertex_exchange_edge_avoidable_check : ∀ e ∈ ten_vertex_exchange_edges, ∃ R ∈ ten_vertex_exchange_edge_avoidable_packings, e ∉ R.biUnion id := by decidetheorem ten_vertex_exchange_edge_avoidable : ∀ e ∈ ten_vertex_exchange_graph.edgeSet, ∃ R : Finset (Finset (Sym2 (Fin 10))), R ⊆ simple_graph_triangle_edge_family ten_vertex_exchange_graph ∧ R.card = 10 ∧ (R : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ e ∉ R.biUnion id := by intro e he have he_edges : e ∈ ten_vertex_exchange_edges := by have h := ten_vertex_exchange_edge_set.1.symm have he' : e ∈ (↑ten_vertex_exchange_edges : Set (Sym2 (Fin 10))) := h ▸ he exact Finset.mem_coe.mp he' obtain ⟨R, hR, heR⟩ := ten_vertex_exchange_edge_avoidable_check e he_edges obtain ⟨hsub, hcard, hdisj⟩ := ten_vertex_exchange_edge_avoidable_packings_valid R hR refine ⟨R, ?_, hcard, hdisj, heR⟩ rw [ten_vertex_exchange_family_eq] exact hsub