AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_finite_witness_facts

theoremverified

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

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.

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

    line 11

      refine ⟨by decide, by decide, by decide, by decide, by decide, by decide, by decide, by decide, ?_⟩
  2. 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.

    lines 12–13

    uses Finset.mem_insert, Finset.mem_singleton

      intro q hq
      simp only [ten_vertex_exchange_packing_q, Finset.mem_insert, Finset.mem_singleton] at hq
  3. 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.

    line 14

      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.

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

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