op_1239_candidate36_max_degree
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
- op_1239_candidate36The simple graph on the 36 vertices Fin 36 with the 35 undirected edges listed in its definition.
- simple_graph_of_edge_list_decidable_relAdjacency in the graph determined by an edge list is decidable.
- Used by 1
- op_1239_subcubic_tree_counterexampleThere exists a tree on Fin 36 with maximum degree at most three whose partial Petrial polynomial is not log-concave.
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.
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.
uses
simple_graph_of_edge_list_decidable_relunfold op_1239_candidate36 exact simple_graph_of_edge_list_decidable_rel _
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.
uses
SimpleGraph.maxDegree_le_of_forall_degree_leapply SimpleGraph.maxDegree_le_of_forall_degree_le intro v
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.
fin_cases v <;> decideThe 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.
uses
Subsingleton.elim,Op1239Degree36.graph_degreehave 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.
- In line 12, `decide` verifies the degree bound for each of the 36 vertices by evaluating neighbor counts algorithmically from the edge list, leaving the combinatorial counting and arithmetic checks implicit in computation.
- Lines 18–20 address a Lean-specific technicality: the main theorem statement parameterizes `maxDegree` with the non-computational instance `Classical.decRel`, whereas the computational check in `graph_degree` requires the explicit algorithmic instance `Op1239Degree36.adjacency`. The step reconciling these two via `Subsingleton.elim` has no paper-mathematics counterpart, where decidability is a property rather than data.
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.
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