ten_vertex_exchange_finite_witness_facts
The explicit edge and triangle lists have sizes 35 and 52; the displayed P and Q are edge-disjoint ten-triangle packings in the list, and Q has no fully singleton-forced triangle relative to that list.
Statement
theorem ten_vertex_exchange_finite_witness_facts : ten_vertex_exchange_edges.card = 35 ∧ ten_vertex_exchange_family.card = 52 ∧ ten_vertex_exchange_packing_p.card = 10 ∧ ten_vertex_exchange_packing_q.card = 10 ∧ ten_vertex_exchange_packing_p ⊆ ten_vertex_exchange_family ∧ ten_vertex_exchange_packing_q ⊆ ten_vertex_exchange_family ∧ (ten_vertex_exchange_packing_p : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ (ten_vertex_exchange_packing_q : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ ∀ q ∈ ten_vertex_exchange_packing_q, ¬ q ⊆ ((ten_vertex_exchange_family.filter (fun t => (t ∩ ten_vertex_exchange_packing_q.biUnion id).card = 1)).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 5
- ten_vertex_exchange_edgesThe 35 unordered edges of the explicit ten-vertex witness.
- ten_vertex_exchange_familyThe explicit list of 52 triangle edge sets for the ten-vertex witness.
- ten_vertex_exchange_packing_pThe selected ten-triangle packing in the local exchange trap.
- ten_vertex_exchange_packing_qThe selected good ten-triangle packing.
- ten_vertex_exchange_triangleThe three edges of a triangle on specified vertices.
- Used by 2
- ten_vertex_exchange_packing_upperThe witness has no packing of eleven edge-disjoint triangles.
- ten_vertex_exchange_edge_setThe witness graph has exactly the 35 listed edges.
The proof, explained
The theorem verifies concrete combinatorial properties of a family of 52 triangles and two 10-triangle packings P and Q in a 10-vertex, 35-edge graph. The first eight conjuncts—establishing the sizes of the edge set, triangle family, and packings, the validity of both packings as subfamilies, and their pairwise edge-disjointness—are resolved by direct finite computation using decide. For the final property, which states that no triangle in Q is fully covered by triangles sharing exactly one edge with Q, the proof expands membership in Q into a ten-way case distinction and verifies each case computationally.
The edge set has size 35, the triangle family has size 52, and P and Q are edge-disjoint packings of size 10 contained in the family.
The first eight conjuncts state decidable properties of explicit finite sets: the cardinalities of the edge set (35), the triangle family (52), and each packing (10), the subset relations P ⊆ family and Q ⊆ family, and the pairwise edge-disjointness of the triangles in P and in Q. The refine tactic dispatches each of these eight subgoals by direct finite computation using decide, leaving only the final non-containment property for Q.
refine ⟨by decide, by decide, by decide, by decide, by decide, by decide, by decide, by decide, ?_⟩
Any triangle q in the packing Q must be one of the ten explicitly defined triangles.
To prove the final universal statement, we introduce an arbitrary triangle q and the assumption that q ∈ Q. Expanding the definition of Q and simplifying finset membership using Finset.mem_insert and Finset.mem_singleton rewrites the membership hypothesis into an explicit ten-way disjunction specifying the concrete vertices of q.
uses
Finset.mem_insert,Finset.mem_singletonintro q hq simp only [ten_vertex_exchange_packing_q, Finset.mem_insert, Finset.mem_singleton] at hq
No triangle in Q is covered by the triangles in the family that share exactly one edge with Q. automation
Performing a case analysis on the ten-way disjunction for q yields ten subgoals, one for each triangle of Q. Substituting the concrete triangle in each case reduces the goal to an explicit edge-level non-containment statement, which decide resolves by exhaustive computation.
rcases hq with h | h | h | h | h | h | h | h | h | h <;> subst q <;> decide
Finset.mem_insert- An element belongs to insert b s (the set {b} ∪ s) if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
- The proof relies on the decide tactic to verify large finite combinatorial statements computationally, which requires the elevated recursion depth and heartbeat limits set at the top of the file.
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.
set_option maxRecDepth 8192set_option maxHeartbeats 3000000theorem ten_vertex_exchange_finite_witness_facts : ten_vertex_exchange_edges.card = 35 ∧ ten_vertex_exchange_family.card = 52 ∧ ten_vertex_exchange_packing_p.card = 10 ∧ ten_vertex_exchange_packing_q.card = 10 ∧ ten_vertex_exchange_packing_p ⊆ ten_vertex_exchange_family ∧ ten_vertex_exchange_packing_q ⊆ ten_vertex_exchange_family ∧ (ten_vertex_exchange_packing_p : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ (ten_vertex_exchange_packing_q : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint ∧ ∀ q ∈ ten_vertex_exchange_packing_q, ¬ q ⊆ ((ten_vertex_exchange_family.filter (fun t => (t ∩ ten_vertex_exchange_packing_q.biUnion id).card = 1)).biUnion id) := by refine ⟨by decide, by decide, by decide, by decide, by decide, by decide, by decide, by decide, ?_⟩ intro q hq simp only [ten_vertex_exchange_packing_q, Finset.mem_insert, Finset.mem_singleton] at hq rcases hq with h | h | h | h | h | h | h | h | h | h <;> subst q <;> decide