AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_packing_upper

theoremverified

The witness has no packing of eleven edge-disjoint triangles.

Statement

theorem ten_vertex_exchange_packing_upper : ∀ R : Finset (Finset (Sym2 (Fin 10))), R ⊆ simple_graph_triangle_edge_family ten_vertex_exchange_graph → (R : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint → R.card ≤ 10
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 11

The proof, explained

The proof bounds the maximum number of edge-disjoint triangles in the 35-edge graph by applying an odd-degree incidence packing bound with a set of 6 odd-degree vertices. Because each triangle in the packing meets every vertex in an even number of edges, each of the 6 odd-degree vertices must lose at least one incident edge to the uncovered edge set, forcing at least ⌈6/2⌉ = 4 uncovered edges (or (6+1)/2 = 3 by integer division). This yields 3|R| + 3 ≤ 35, which forces |R| ≤ 10.

  1. Every triangle in the 52-triangle candidate family is a subgraph of the 35-edge graph and has size 3. automation

    Exhaustive case analysis over all 52 triangles in the family, verifying each one by computation.

    lines 6–8

    uses Finset.mem_insert, Finset.mem_singleton

      intro t ht
      simp only [ten_vertex_exchange_family, Finset.mem_insert, Finset.mem_singleton] at ht
      rcases ht with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst t <;> decide
  2. Every vertex is incident to an even number of edges (0 or 2) in every triangle of the family. automation

    Exhaustive check across all 10 vertices and all 52 triangles, verified by computation.

    lines 12–14

    uses Finset.mem_insert, Finset.mem_singleton

      intro v t ht
      simp only [ten_vertex_exchange_family, Finset.mem_insert, Finset.mem_singleton] at ht
      rcases ht with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst t <;> fin_cases v <;> decide
  3. Vertices 0, 4, 5, 6, 7, and 8 have odd degree in the graph. automation

    The degrees of these 6 vertices are verified to be odd by direct computation.

    line 17

        ∀ v ∈ ({0,4,5,6,7,8} : Finset (Fin 10)), Odd ((ten_vertex_exchange_edges.filter (fun e => v ∈ e)).card) := by decide
  4. The packing R is a collection of triangles from the explicit 52-triangle family.

    We introduce the packing R and its pairwise disjointness, and rewrite its triangles into the explicit family using the equivalence theorem ten_vertex_exchange_family_eq.

    lines 23–25

    uses ten_vertex_exchange_family_eq

      intro R hR hdisj
      have hF := ten_vertex_exchange_family_eq
      have hRF : R ⊆ ten_vertex_exchange_family := by simpa only [hF] using hR
  5. The general odd-degree incidence packing bound applies to R.

    Applying finite_edge_packing_odd_incidence_bound with the set of 6 odd-degree vertices O = {0, 4, 5, 6, 7, 8}, using the verified triangle properties, gives 3|R| + (|O|+1)/2 ≤ |E|.

    lines 26–29

    uses In732Upper.in732_triangle_data, In732Upper.in732_incidence_data, In732Upper.in732_odd_data, finite_edge_packing_odd_incidence_bound

      have hb := finite_edge_packing_odd_incidence_bound ten_vertex_exchange_edges R ({0,4,5,6,7,8} : Finset (Fin 10))
        (fun t ht => (in732_triangle_data t (hRF ht)).1) hdisj
        (fun t ht => (in732_triangle_data t (hRF ht)).2)
        (fun v t ht => in732_incidence_data v t (hRF ht)) in732_odd_data
  6. The total edge count is 35 and the odd vertex set has size 6. automation

    The edge set cardinality is fetched from ten_vertex_exchange_finite_witness_facts.1, and the odd set size is evaluated by decision procedure.

    lines 30–31

    uses ten_vertex_exchange_finite_witness_facts.1

      have hE : ten_vertex_exchange_edges.card = 35 := ten_vertex_exchange_finite_witness_facts.1
      have hO : ({0,4,5,6,7,8} : Finset (Fin 10)).card = 6 := by decide
  7. The packing R has size at most 10. automation

    Substituting |E| = 35 and |O| = 6 into the bound gives 3|R| + 3 ≤ 35, whence integer linear arithmetic deduces |R| ≤ 10.

    lines 32–33

      rw [hE,hO] at hb
      omega
In732Upper.in732_triangle_data
Every candidate triangle in the 10-vertex exchange family consists of 3 edges of the graph.
In732Upper.in732_incidence_data
For every vertex and every triangle in the family, the number of edges of the triangle incident to that vertex is even (either 0 or 2).
In732Upper.in732_odd_data
The vertices 0, 4, 5, 6, 7, and 8 each have odd degree in the graph.
finite_edge_packing_odd_incidence_bound
In any graph, an edge-disjoint packing of triangles leaves at least ⌈|O|/2⌉ edges uncovered, where O is any set of vertices of odd degree; thus 3|P| + (|O|+1)/2 ≤ |E|.
ten_vertex_exchange_family_eq
The triangle family of the 10-vertex exchange graph is exactly the explicit 52-triangle family.
ten_vertex_exchange_finite_witness_facts.1
The 10-vertex exchange graph has 35 edges.

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

Lean’s trace was cut to the first 400 of 745 tactics.

set_option maxRecDepth 8192set_option maxHeartbeats 3000000namespace In732Uppertheorem in732_triangle_data :    ∀ t ∈ ten_vertex_exchange_family, t ⊆ ten_vertex_exchange_edges ∧ t.card = 3 := by  intro t ht  simp only [ten_vertex_exchange_family, Finset.mem_insert, Finset.mem_singleton] at ht  rcases ht with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst t <;> decidetheorem in732_incidence_data :    ∀ v : Fin 10, ∀ t ∈ ten_vertex_exchange_family, Even ((t.filter (fun e => v ∈ e)).card) := by  intro v t ht  simp only [ten_vertex_exchange_family, Finset.mem_insert, Finset.mem_singleton] at ht  rcases ht with h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h | h <;> subst t <;> fin_cases v <;> decidetheorem in732_odd_data :    ∀ v ∈ ({0,4,5,6,7,8} : Finset (Fin 10)), Odd ((ten_vertex_exchange_edges.filter (fun e => v ∈ e)).card) := by decideend In732Upperopen In732Uppertheorem ten_vertex_exchange_packing_upper : ∀ R : Finset (Finset (Sym2 (Fin 10))), R ⊆ simple_graph_triangle_edge_family ten_vertex_exchange_graph → (R : Set (Finset (Sym2 (Fin 10)))).Pairwise Disjoint → R.card ≤ 10 := by  intro R hR hdisj  have hF := ten_vertex_exchange_family_eq  have hRF : R ⊆ ten_vertex_exchange_family := by simpa only [hF] using hR  have hb := finite_edge_packing_odd_incidence_bound ten_vertex_exchange_edges R ({0,4,5,6,7,8} : Finset (Fin 10))    (fun t ht => (in732_triangle_data t (hRF ht)).1) hdisj    (fun t ht => (in732_triangle_data t (hRF ht)).2)    (fun v t ht => in732_incidence_data v t (hRF ht)) in732_odd_data  have hE : ten_vertex_exchange_edges.card = 35 := ten_vertex_exchange_finite_witness_facts.1  have hO : ({0,4,5,6,7,8} : Finset (Fin 10)).card = 6 := by decide  rw [hE,hO] at hb  omega
See it in the graphDiscuss this resultChallenge it