AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_edge_set

theoremverified

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
Used by 4

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.

  1. 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`.

    line 2

    uses ten_vertex_exchange_finite_witness_facts.1

      refine ⟨?_, ten_vertex_exchange_finite_witness_facts.1⟩
  2. 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`.

    lines 3–4

    uses SimpleGraph.edgeSet_fromEdgeSet

      unfold ten_vertex_exchange_graph
      rw [SimpleGraph.edgeSet_fromEdgeSet]
  3. 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}$.

    lines 5–6

    uses SetLike.mem_coe, Set.mem_sdiff, Sym2.mem_diagSet, iff_self_and

      ext x
      simp only [SetLike.mem_coe, Set.mem_sdiff, Sym2.mem_diagSet, iff_self_and]
  4. 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.

    lines 7–8

      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`.

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

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
See it in the graphDiscuss this resultChallenge it