ten_vertex_exchange_edge_set
The witness graph has exactly the 35 listed edges.
Statement
theorem ten_vertex_exchange_edge_set : (↑ten_vertex_exchange_edges : Set (Sym2 (Fin 10))) = ten_vertex_exchange_graph.edgeSet ∧ ten_vertex_exchange_edges.card = 35- 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 6
- 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_finite_witness_factsThe 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…
- 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_packing_pThe selected ten-triangle packing in the local exchange trap.
- Used by 4
- ten_vertex_exchange_packing_upperThe witness has no packing of eleven edge-disjoint triangles.
- ten_vertex_exchange_edge_avoidableFor each of the 35 edges, a ten-triangle packing avoids that edge.
- ten_vertex_exchange_triangle_connectedAfter excluding each graph edge, the triangle family is connected under sharing any other edge.
- ten_vertex_exchange_codegreeEach edge of the witness lies in at least three triangles.
The proof, explained
The theorem establishes that the witness graph's edge set matches the 35 listed edges and has cardinality 35. The cardinality claim is supplied directly from an existing lemma, while the edge set equality follows because `SimpleGraph.fromEdgeSet` only discards self-loops, and an exhaustive computational check confirms that none of the 35 listed edges are loops.
The statement splits into two parts: the edge count is 35 (discharged immediately), leaving the equality of edge sets to be shown.
We split the conjunction using `refine`. The second conjunct, stating that `ten_vertex_exchange_edges.card = 35`, is provided directly by `ten_vertex_exchange_finite_witness_facts.1`.
uses
ten_vertex_exchange_finite_witness_facts.1refine ⟨?_, ten_vertex_exchange_finite_witness_facts.1⟩The edge set equality reduces to showing that `ten_vertex_exchange_edges` equals itself minus the diagonal set of self-loops.
Unfolding `ten_vertex_exchange_graph` reveals that it is defined via `SimpleGraph.fromEdgeSet`. Rewriting with `SimpleGraph.edgeSet_fromEdgeSet` replaces the graph's edge set with the original set of pairs minus `Sym2.diagSet`.
uses
SimpleGraph.edgeSet_fromEdgeSetunfold ten_vertex_exchange_graph rw [SimpleGraph.edgeSet_fromEdgeSet]
It suffices to show that every edge in `ten_vertex_exchange_edges` is non-diagonal (has distinct endpoints).
Using set extensionality (`ext x`), two sets are equal if an arbitrary pair $x$ belongs to one if and only if it belongs to the other. Rewriting with `Set.mem_sdiff`, `Sym2.mem_diagSet`, and `SetLike.mem_coe` turns this into $x \in S \leftrightarrow (x \in S \wedge \neg x.\text{IsDiag})$, which `iff_self_and` simplifies to $x \in S \to \neg x.\text{IsDiag}$.
uses
SetLike.mem_coe,Set.mem_sdiff,Sym2.mem_diagSet,iff_self_andext x simp only [SetLike.mem_coe, Set.mem_sdiff, Sym2.mem_diagSet, iff_self_and]
No listed edge is a self-loop, completing the proof. automation
We introduce the auxiliary lemma `hdiag` stating that none of the elements in `ten_vertex_exchange_edges` are diagonal. Because `ten_vertex_exchange_edges` is an explicit finite collection of 35 vertex pairs, `decide` proves this by exhaustive evaluation. Specializing `hdiag` to $x$ completes the proof.
have hdiag : ∀ y ∈ ten_vertex_exchange_edges, ¬y.IsDiag := by decide exact hdiag x
ten_vertex_exchange_finite_witness_facts.1- The first conjunct of `ten_vertex_exchange_finite_witness_facts`, asserting that the set `ten_vertex_exchange_edges` has cardinality 35.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of `SimpleGraph.fromEdgeSet s` is the set `s` minus the diagonal pairs (self-loops).
SetLike.mem_coe- Membership in a coerced collection is equivalent to membership in the underlying collection.
Set.mem_sdiff- An element is in the set difference `s \ t` if and only if it is in `s` and not in `t`.
Sym2.mem_diagSet- An unordered pair belongs to `Sym2.diagSet` if and only if it is a diagonal pair (a self-loop).
iff_self_and- The equivalence `(p ↔ p ∧ q)` is logically equivalent to the implication `p → q`.
- The non-diagonality of all 35 explicit edges is checked entirely by kernel computation via `decide`.
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.
theorem ten_vertex_exchange_edge_set : (↑ten_vertex_exchange_edges : Set (Sym2 (Fin 10))) = ten_vertex_exchange_graph.edgeSet ∧ ten_vertex_exchange_edges.card = 35 := by refine ⟨?_, ten_vertex_exchange_finite_witness_facts.1⟩ unfold ten_vertex_exchange_graph rw [SimpleGraph.edgeSet_fromEdgeSet] ext x simp only [SetLike.mem_coe, Set.mem_sdiff, Sym2.mem_diagSet, iff_self_and] have hdiag : ∀ y ∈ ten_vertex_exchange_edges, ¬y.IsDiag := by decide exact hdiag x