AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_edge_avoidable

theoremverified

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

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.

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

    lines 18–20

    uses ten_vertex_exchange_edge_avoidable_packings, List.mem_cons, List.not_mem_nil, or_false

      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 <;> decide
  2. 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.

    line 24

      decide
  3. Any 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`.

    lines 27–31

    uses ten_vertex_exchange_edge_set.1.symm, Finset.mem_coe.mp

      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'
  4. 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.

    lines 32–33

    uses ten_vertex_exchange_edge_avoidable_check, ten_vertex_exchange_edge_avoidable_packings_valid

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

    lines 34–36

    uses ten_vertex_exchange_family_eq

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

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

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