AFTD Auto-Formalizing Theoretical Domains

ten_vertex_exchange_codegree

theoremverified

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

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

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

    line 2

    uses ten_vertex_exchange_family_eq, ten_vertex_exchange_edge_set.1

      rw [ten_vertex_exchange_family_eq, ← ten_vertex_exchange_edge_set.1]
  2. 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.

    line 3

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

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

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