op_1239_candidate36_tree
The graph op_1239_candidate36 is a tree.
Statement
theorem op_1239_candidate36_tree : op_1239_candidate36.IsTree- 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 3
- 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.
- Arena.Reachable.transReachability is transitive.
- 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 shows that the 36-vertex graph op_1239_candidate36 is a tree using the standard theorem that a finite graph is a tree if and only if it is connected and |E| + 1 = |V|. Connectedness is established by taking vertex 0 as a root and constructing explicit paths from 0 to all other 35 vertices along edges verified computationally from the edge list, followed by an exhaustive case check across all vertices in Fin 36. The graph is then verified to have exactly 35 edges. Combining connectedness with the arithmetic identity 35 + 1 = 36 concludes that the graph is a tree.
Adjacency in op_1239_candidate36 is decidable.
Unfolding the definition of op_1239_candidate36 expresses the graph in terms of its explicit list of edges. Adjacency in any graph defined by an edge list is decidable via simple_graph_of_edge_list_decidable_rel.
uses
simple_graph_of_edge_list_decidable_relunfold op_1239_candidate36 exact simple_graph_of_edge_list_decidable_rel _
Connectedness of the graph reduces to showing that every vertex is reachable from vertex 0.
By SimpleGraph.connected_iff_exists_forall_reachable, a graph is connected if and only if there is a vertex that can reach every vertex. Vertex 0 is chosen as this root vertex.
uses
SimpleGraph.connected_iff_exists_forall_reachableapply (SimpleGraph.connected_iff_exists_forall_reachable _).2 use (0 : Fin 36)
Vertex 0 can reach every other vertex 1, ..., 35 along paths in the graph.
For each vertex w from 1 to 35, a path from 0 is built iteratively: an edge connecting an already reached vertex to w is confirmed by computing directly on the edge list, and reachability is extended to w by transitivity.
have h1 : op_1239_candidate36.Reachable 0 1 := (show op_1239_candidate36.Adj 0 1 from by decide).reachable have h3 : op_1239_candidate36.Reachable 0 3 := (show op_1239_candidate36.Adj 0 3 from by decide).reachable have h8 : op_1239_candidate36.Reachable 0 8 := (show op_1239_candidate36.Adj 0 8 from by decide).reachable have h2 : op_1239_candidate36.Reachable 0 2 := h1.trans (show op_1239_candidate36.Adj 1 2 from by decide).reachable have h4 : op_1239_candidate36.Reachable 0 4 := h1.trans (show op_1239_candidate36.Adj 1 4 from by decide).reachable have h5 : op_1239_candidate36.Reachable 0 5 := h3.trans (show op_1239_candidate36.Adj 3 5 from by decide).reachable have h21 : op_1239_candidate36.Reachable 0 21 := h3.trans (show op_1239_candidate36.Adj 3 21 from by decide).reachable have h11 : op_1239_candidate36.Reachable 0 11 := h8.trans (show op_1239_candidate36.Adj 8 11 from by decide).reachable have h26 : op_1239_candidate36.Reachable 0 26 := h8.trans (show op_1239_candidate36.Adj 8 26 from by decide).reachable have h6 : op_1239_candidate36.Reachable 0 6 := h2.trans (show op_1239_candidate36.Adj 2 6 from by decide).reachable have h7 : op_1239_candidate36.Reachable 0 7 := h2.trans (show op_1239_candidate36.Adj 2 7 from by decide).reachable have h12 : op_1239_candidate36.Reachable 0 12 := h4.trans (show op_1239_candidate36.Adj 4 12 from by decide).reachable have h16 : op_1239_candidate36.Reachable 0 16 := h4.trans (show op_1239_candidate36.Adj 4 16 from by decide).reachable have h13 : op_1239_candidate36.Reachable 0 13 := h5.trans (show op_1239_candidate36.Adj 5 13 from by decide).reachable have h14 : op_1239_candidate36.Reachable 0 14 := h5.trans (show op_1239_candidate36.Adj 5 14 from by decide).reachable have h27 : op_1239_candidate36.Reachable 0 27 := h11.trans (show op_1239_candidate36.Adj 11 27 from by decide).reachable have h33 : op_1239_candidate36.Reachable 0 33 := h11.trans (show op_1239_candidate36.Adj 11 33 from by decide).reachable have h9 : op_1239_candidate36.Reachable 0 9 := h6.trans (show op_1239_candidate36.Adj 6 9 from by decide).reachable have h18 : op_1239_candidate36.Reachable 0 18 := h6.trans (show op_1239_candidate36.Adj 6 18 from by decide).reachable have h10 : op_1239_candidate36.Reachable 0 10 := h7.trans (show op_1239_candidate36.Adj 7 10 from by decide).reachable have h15 : op_1239_candidate36.Reachable 0 15 := h7.trans (show op_1239_candidate36.Adj 7 15 from by decide).reachable have h22 : op_1239_candidate36.Reachable 0 22 := h12.trans (show op_1239_candidate36.Adj 12 22 from by decide).reachable have h20 : op_1239_candidate36.Reachable 0 20 := h16.trans (show op_1239_candidate36.Adj 16 20 from by decide).reachable have h31 : op_1239_candidate36.Reachable 0 31 := h16.trans (show op_1239_candidate36.Adj 16 31 from by decide).reachable have h17 : op_1239_candidate36.Reachable 0 17 := h13.trans (show op_1239_candidate36.Adj 13 17 from by decide).reachable have h24 : op_1239_candidate36.Reachable 0 24 := h14.trans (show op_1239_candidate36.Adj 14 24 from by decide).reachable have h29 : op_1239_candidate36.Reachable 0 29 := h18.trans (show op_1239_candidate36.Adj 18 29 from by decide).reachable have h32 : op_1239_candidate36.Reachable 0 32 := h18.trans (show op_1239_candidate36.Adj 18 32 from by decide).reachable have h19 : op_1239_candidate36.Reachable 0 19 := h10.trans (show op_1239_candidate36.Adj 10 19 from by decide).reachable have h30 : op_1239_candidate36.Reachable 0 30 := h10.trans (show op_1239_candidate36.Adj 10 30 from by decide).reachable have h23 : op_1239_candidate36.Reachable 0 23 := h20.trans (show op_1239_candidate36.Adj 20 23 from by decide).reachable have h28 : op_1239_candidate36.Reachable 0 28 := h20.trans (show op_1239_candidate36.Adj 20 28 from by decide).reachable have h35 : op_1239_candidate36.Reachable 0 35 := h29.trans (show op_1239_candidate36.Adj 29 35 from by decide).reachable have h25 : op_1239_candidate36.Reachable 0 25 := h23.trans (show op_1239_candidate36.Adj 23 25 from by decide).reachable have h34 : op_1239_candidate36.Reachable 0 34 := h28.trans (show op_1239_candidate36.Adj 28 34 from by decide).reachable
The graph op_1239_candidate36 is connected.
Given any vertex v, an exhaustive case analysis over Fin 36 checks all 36 possibilities. Vertex 0 is reachable from itself by reflexivity (SimpleGraph.Reachable.rfl), and each vertex 1 through 35 is reachable by the corresponding path established previously. Since 0 can reach all vertices, the graph is connected.
uses
SimpleGraph.Reachable.rflintro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h1 · exact h2 · exact h3 · exact h4 · exact h5 · exact h6 · exact h7 · exact h8 · exact h9 · exact h10 · exact h11 · exact h12 · exact h13 · exact h14 · exact h15 · exact h16 · exact h17 · exact h18 · exact h19 · exact h20 · exact h21 · exact h22 · exact h23 · exact h24 · exact h25 · exact h26 · exact h27 · exact h28 · exact h29 · exact h30 · exact h31 · exact h32 · exact h33 · exact h34 · exact h35
The graph has exactly 35 edges. automation
The number of edges in the graph is evaluated directly by counting the edges in the defining list using Lean's decision procedure.
theorem graph_edges : op_1239_candidate36.edgeFinset.card = 35 := by decide
The graph satisfies the tree characterization: it is connected and has |E| + 1 = |V|.
By SimpleGraph.isTree_iff_connected_and_card, a finite graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices. Connectedness is provided by Op1239Tree36.graph_connected. Rewriting the cardinalities using Nat.card_eq_fintype_card and SimpleGraph.edgeFinset_card reduces the edge condition to 35 + 1 = 36, which holds using the edge count from Op1239Tree36.graph_edges.
uses
SimpleGraph.isTree_iff_connected_and_card,Op1239Tree36.graph_connected,Nat.card_eq_fintype_card,SimpleGraph.edgeFinset_card,Op1239Tree36.graph_edgesapply (SimpleGraph.isTree_iff_connected_and_card).2 refine ⟨Op1239Tree36.graph_connected, ?_⟩ rw [Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card] simp [Op1239Tree36.graph_edges]
simple_graph_of_edge_list_decidable_rel- Adjacency in a simple graph defined from an explicit list of edges is decidable.
SimpleGraph.connected_iff_exists_forall_reachable- A graph is connected if and only if there exists a vertex from which every vertex is reachable.
SimpleGraph.Reachable.rfl- Every vertex is reachable from itself.
SimpleGraph.isTree_iff_connected_and_card- A finite graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices.
Op1239Tree36.graph_connected- The graph op_1239_candidate36 is connected.
Nat.card_eq_fintype_card- For a finite type, its cardinality as a natural number equals its Fintype cardinality.
SimpleGraph.edgeFinset_card- The number of elements in the edge finset equals the cardinality of the edge set as a finite type.
Op1239Tree36.graph_edges- The graph op_1239_candidate36 has exactly 35 edges.
- Checking edge adjacencies and computing the edge set cardinality are handled automatically by Lean's decide tactic via computational reflection on the concrete list of edges.
- The DecidableRel instance at the beginning is a formal prerequisite enabling the decide tactic to evaluate edge adjacencies computationally.
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 Op1239Tree36instance : 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_connected : op_1239_candidate36.Connected := by apply (SimpleGraph.connected_iff_exists_forall_reachable _).2 use (0 : Fin 36) have h1 : op_1239_candidate36.Reachable 0 1 := (show op_1239_candidate36.Adj 0 1 from by decide).reachable have h3 : op_1239_candidate36.Reachable 0 3 := (show op_1239_candidate36.Adj 0 3 from by decide).reachable have h8 : op_1239_candidate36.Reachable 0 8 := (show op_1239_candidate36.Adj 0 8 from by decide).reachable have h2 : op_1239_candidate36.Reachable 0 2 := h1.trans (show op_1239_candidate36.Adj 1 2 from by decide).reachable have h4 : op_1239_candidate36.Reachable 0 4 := h1.trans (show op_1239_candidate36.Adj 1 4 from by decide).reachable have h5 : op_1239_candidate36.Reachable 0 5 := h3.trans (show op_1239_candidate36.Adj 3 5 from by decide).reachable have h21 : op_1239_candidate36.Reachable 0 21 := h3.trans (show op_1239_candidate36.Adj 3 21 from by decide).reachable have h11 : op_1239_candidate36.Reachable 0 11 := h8.trans (show op_1239_candidate36.Adj 8 11 from by decide).reachable have h26 : op_1239_candidate36.Reachable 0 26 := h8.trans (show op_1239_candidate36.Adj 8 26 from by decide).reachable have h6 : op_1239_candidate36.Reachable 0 6 := h2.trans (show op_1239_candidate36.Adj 2 6 from by decide).reachable have h7 : op_1239_candidate36.Reachable 0 7 := h2.trans (show op_1239_candidate36.Adj 2 7 from by decide).reachable have h12 : op_1239_candidate36.Reachable 0 12 := h4.trans (show op_1239_candidate36.Adj 4 12 from by decide).reachable have h16 : op_1239_candidate36.Reachable 0 16 := h4.trans (show op_1239_candidate36.Adj 4 16 from by decide).reachable have h13 : op_1239_candidate36.Reachable 0 13 := h5.trans (show op_1239_candidate36.Adj 5 13 from by decide).reachable have h14 : op_1239_candidate36.Reachable 0 14 := h5.trans (show op_1239_candidate36.Adj 5 14 from by decide).reachable have h27 : op_1239_candidate36.Reachable 0 27 := h11.trans (show op_1239_candidate36.Adj 11 27 from by decide).reachable have h33 : op_1239_candidate36.Reachable 0 33 := h11.trans (show op_1239_candidate36.Adj 11 33 from by decide).reachable have h9 : op_1239_candidate36.Reachable 0 9 := h6.trans (show op_1239_candidate36.Adj 6 9 from by decide).reachable have h18 : op_1239_candidate36.Reachable 0 18 := h6.trans (show op_1239_candidate36.Adj 6 18 from by decide).reachable have h10 : op_1239_candidate36.Reachable 0 10 := h7.trans (show op_1239_candidate36.Adj 7 10 from by decide).reachable have h15 : op_1239_candidate36.Reachable 0 15 := h7.trans (show op_1239_candidate36.Adj 7 15 from by decide).reachable have h22 : op_1239_candidate36.Reachable 0 22 := h12.trans (show op_1239_candidate36.Adj 12 22 from by decide).reachable have h20 : op_1239_candidate36.Reachable 0 20 := h16.trans (show op_1239_candidate36.Adj 16 20 from by decide).reachable have h31 : op_1239_candidate36.Reachable 0 31 := h16.trans (show op_1239_candidate36.Adj 16 31 from by decide).reachable have h17 : op_1239_candidate36.Reachable 0 17 := h13.trans (show op_1239_candidate36.Adj 13 17 from by decide).reachable have h24 : op_1239_candidate36.Reachable 0 24 := h14.trans (show op_1239_candidate36.Adj 14 24 from by decide).reachable have h29 : op_1239_candidate36.Reachable 0 29 := h18.trans (show op_1239_candidate36.Adj 18 29 from by decide).reachable have h32 : op_1239_candidate36.Reachable 0 32 := h18.trans (show op_1239_candidate36.Adj 18 32 from by decide).reachable have h19 : op_1239_candidate36.Reachable 0 19 := h10.trans (show op_1239_candidate36.Adj 10 19 from by decide).reachable have h30 : op_1239_candidate36.Reachable 0 30 := h10.trans (show op_1239_candidate36.Adj 10 30 from by decide).reachable have h23 : op_1239_candidate36.Reachable 0 23 := h20.trans (show op_1239_candidate36.Adj 20 23 from by decide).reachable have h28 : op_1239_candidate36.Reachable 0 28 := h20.trans (show op_1239_candidate36.Adj 20 28 from by decide).reachable have h35 : op_1239_candidate36.Reachable 0 35 := h29.trans (show op_1239_candidate36.Adj 29 35 from by decide).reachable have h25 : op_1239_candidate36.Reachable 0 25 := h23.trans (show op_1239_candidate36.Adj 23 25 from by decide).reachable have h34 : op_1239_candidate36.Reachable 0 34 := h28.trans (show op_1239_candidate36.Adj 28 34 from by decide).reachable intro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h1 · exact h2 · exact h3 · exact h4 · exact h5 · exact h6 · exact h7 · exact h8 · exact h9 · exact h10 · exact h11 · exact h12 · exact h13 · exact h14 · exact h15 · exact h16 · exact h17 · exact h18 · exact h19 · exact h20 · exact h21 · exact h22 · exact h23 · exact h24 · exact h25 · exact h26 · exact h27 · exact h28 · exact h29 · exact h30 · exact h31 · exact h32 · exact h33 · exact h34 · exact h35theorem graph_edges : op_1239_candidate36.edgeFinset.card = 35 := by decideend Op1239Tree36theorem op_1239_candidate36_tree : op_1239_candidate36.IsTree := by apply (SimpleGraph.isTree_iff_connected_and_card).2 refine ⟨Op1239Tree36.graph_connected, ?_⟩ rw [Nat.card_eq_fintype_card, ← SimpleGraph.edgeFinset_card] simp [Op1239Tree36.graph_edges]