ten_vertex_exchange_codegree
Each edge of the witness lies in at least three triangles.
Statement
theorem ten_vertex_exchange_codegree : ∀ e ∈ ten_vertex_exchange_graph.edgeSet, 3 ≤ ((simple_graph_triangle_edge_family ten_vertex_exchange_graph).filter (fun t => e ∈ t)).card
- 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
- 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.
- 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.
The proof, explained
This theorem establishes that every edge of the 10-vertex exchange graph has codegree at least 3, meaning each edge is contained in at least three triangles. The proof replaces the abstract edge set and triangle family with their explicitly defined finite representations. Once rephrased as a finite search over 35 concrete edges, the claim is verified by exhaustive computation via `decide`.
It suffices to check the codegree condition for each edge in the concrete finite set `ten_vertex_exchange_edges` using the explicit triangle family `ten_vertex_exchange_family`.
We rewrite the edge set and triangle family of the graph into their concrete finite definitions using `ten_vertex_exchange_family_eq` and the first component of `ten_vertex_exchange_edge_set`. This replaces abstract graph-theoretic objects with explicit, computable finite sets.
uses
ten_vertex_exchange_family_eq,ten_vertex_exchange_edge_set.1rw [ten_vertex_exchange_family_eq, ← ten_vertex_exchange_edge_set.1]Each edge in `ten_vertex_exchange_edges` is contained in at least three triangles of `ten_vertex_exchange_family`. automation
Because the edge set has only 35 elements and the triangle family is an explicit finite set of triples, the condition ∀ e ∈ ten_vertex_exchange_edges, 3 ≤ |{t ∈ ten_vertex_exchange_family | e ∈ t}| is a decidable proposition on finite data. The `decide` tactic evaluates this condition by exhaustive computation.
decide
ten_vertex_exchange_family_eq- The triangle edge family of the 10-vertex exchange graph is equal to the explicitly enumerated finite set of triangles `ten_vertex_exchange_family`.
ten_vertex_exchange_edge_set.1- The edge set of the 10-vertex exchange graph is identical to the coercion of the explicit 35-element finset `ten_vertex_exchange_edges`.
- The verification that each of the 35 edges belongs to at least 3 triangles is delegated entirely to Lean's kernel computation (`decide`) rather than a symbolic pen-and-paper proof.
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.
theorem ten_vertex_exchange_codegree : ∀ e ∈ ten_vertex_exchange_graph.edgeSet, 3 ≤ ((simple_graph_triangle_edge_family ten_vertex_exchange_graph).filter (fun t => e ∈ t)).card := by rw [ten_vertex_exchange_family_eq, ← ten_vertex_exchange_edge_set.1] decide