ten_vertex_exchange_packing_upper
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
- ten_vertex_exchange_graphThe simple graph built from the explicit ten-vertex edge set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- ten_vertex_exchange_edge_setThe witness graph has exactly the 35 listed edges.
- finite_edge_packing_odd_incidence_boundFor a finite set of undirected edges E and a pairwise edge-disjoint family P of three-edge sets, if each member of P has even incidence at…
- 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_edgesThe 35 unordered edges of the explicit ten-vertex witness.
- ten_vertex_exchange_familyThe explicit list of 52 triangle edge sets for the ten-vertex witness.
- ten_vertex_exchange_packing_qThe selected good ten-triangle packing.
- ten_vertex_exchange_triangleThe three edges of a triangle on specified vertices.
- ten_vertex_exchange_packing_pThe selected ten-triangle packing in the local exchange trap.
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.
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.
uses
Finset.mem_insert,Finset.mem_singletonintro 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
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.
uses
Finset.mem_insert,Finset.mem_singletonintro 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
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.
∀ v ∈ ({0,4,5,6,7,8} : Finset (Fin 10)), Odd ((ten_vertex_exchange_edges.filter (fun e => v ∈ e)).card) := by decideThe 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.
uses
ten_vertex_exchange_family_eqintro R hR hdisj have hF := ten_vertex_exchange_family_eq have hRF : R ⊆ ten_vertex_exchange_family := by simpa only [hF] using hR
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|.
uses
In732Upper.in732_triangle_data,In732Upper.in732_incidence_data,In732Upper.in732_odd_data,finite_edge_packing_odd_incidence_boundhave 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
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.
uses
ten_vertex_exchange_finite_witness_facts.1have 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
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.
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
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.
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