AFTD Auto-Formalizing Theoretical Domains

op_1239_candidate36_max_degree

theoremverified

The maximum degree of op_1239_candidate36 is at most 3.

Statement

theorem op_1239_candidate36_max_degree : letI : DecidableRel op_1239_candidate36.Adj := Classical.decRel _; op_1239_candidate36.maxDegree ≤ 3
Source
Candidate for OP-1239; computations 28328 and 28332 checks the standard leaf-deletion recurrence from arXiv:2611.07503, Lemma 1.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof establishes that the graph `op_1239_candidate36` has maximum degree at most 3 by reducing the maximum degree bound to checking each vertex individually. Since the graph has 36 vertices and is explicitly specified by a list of 35 edges, the degree of every vertex is verified to be at most 3 by exhaustive finite computation. Finally, because the theorem is stated in terms of classical decidability while the computation uses a constructive decision procedure, the proof bridges the two using proof irrelevance for subsingletons.

  1. Adjacency of vertices in `op_1239_candidate36` is decidable.

    We unfold the definition of `op_1239_candidate36`, which represents a graph built from an explicit list of 35 edges, and apply `simple_graph_of_edge_list_decidable_rel` to equip the graph with an algorithmic adjacency decision procedure.

    lines 3–4

    uses simple_graph_of_edge_list_decidable_rel

      unfold op_1239_candidate36
      exact simple_graph_of_edge_list_decidable_rel _
  2. To show that the graph has maximum degree at most 3, it suffices to show that each vertex has degree at most 3.

    Applying `SimpleGraph.maxDegree_le_of_forall_degree_le` with k = 3 reduces bounding the maximum degree to showing that an arbitrary vertex v has degree at most 3. We introduce the vertex v.

    lines 10–11

    uses SimpleGraph.maxDegree_le_of_forall_degree_le

      apply SimpleGraph.maxDegree_le_of_forall_degree_le
      intro v
  3. Every vertex in `op_1239_candidate36` has degree at most 3, completing the proof of `Op1239Degree36.graph_degree`. automation

    The vertex type is `Fin 36`, which has exactly 36 elements. The tactic `fin_cases` performs a case analysis over all 36 vertices (0 through 35), and for each vertex, `decide` counts its incident edges in the edge list and verifies by finite computation that the degree is at most 3.

    line 12

      fin_cases v <;> decide
  4. The maximum degree bound holds under the classical decidability instance, completing the proof of `op_1239_candidate36_max_degree`.

    The main theorem is stated using Lean's classical decider `Classical.decRel`, whereas `Op1239Degree36.graph_degree` was established with the algorithmic decider `Op1239Degree36.adjacency`. Because `DecidableRel` is a subsingleton, any two decision procedures are equal by `Subsingleton.elim`. Rewriting with this equality allows us to apply `Op1239Degree36.graph_degree` to close the goal.

    lines 18–20

    uses Subsingleton.elim, Op1239Degree36.graph_degree

      have h : Classical.decRel op_1239_candidate36.Adj = (Op1239Degree36.adjacency : DecidableRel op_1239_candidate36.Adj) := Subsingleton.elim _ _
      rw [h]
      exact Op1239Degree36.graph_degree
simple_graph_of_edge_list_decidable_rel
For any graph defined from an explicit list of edges, the adjacency relation between vertices is algorithmically decidable.
SimpleGraph.maxDegree_le_of_forall_degree_le
If every vertex in a graph has degree at most k, then the maximum degree of the graph is at most k.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
Op1239Degree36.graph_degree
The maximum degree of `op_1239_candidate36` is at most 3 when using the computational adjacency instance.

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

namespace Op1239Degree36instance adjacency : DecidableRel op_1239_candidate36.Adj := by  unfold op_1239_candidate36  exact simple_graph_of_edge_list_decidable_rel _set_option maxRecDepth 100000set_option maxHeartbeats 0theorem graph_degree : op_1239_candidate36.maxDegree ≤ 3 := by  apply SimpleGraph.maxDegree_le_of_forall_degree_le  intro v  fin_cases v <;> decideend Op1239Degree36theorem op_1239_candidate36_max_degree : letI : DecidableRel op_1239_candidate36.Adj := Classical.decRel _; op_1239_candidate36.maxDegree ≤ 3 := by  have h : Classical.decRel op_1239_candidate36.Adj = (Op1239Degree36.adjacency : DecidableRel op_1239_candidate36.Adj) := Subsingleton.elim _ _  rw [h]  exact Op1239Degree36.graph_degree
See it in the graphDiscuss this resultChallenge it