AFTD Auto-Formalizing Theoretical Domains

op_1239_candidate36_tree

theoremverified

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
Used by 1

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.

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

    lines 3–4

    uses simple_graph_of_edge_list_decidable_rel

      unfold op_1239_candidate36
      exact simple_graph_of_edge_list_decidable_rel _
  2. 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.

    lines 10–11

    uses SimpleGraph.connected_iff_exists_forall_reachable

      apply (SimpleGraph.connected_iff_exists_forall_reachable _).2
      use (0 : Fin 36)
  3. 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.

    lines 12–46

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

    lines 47–84

    uses SimpleGraph.Reachable.rfl

      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 h35
  5. 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.

    line 86

    theorem graph_edges : op_1239_candidate36.edgeFinset.card = 35 := by decide
  6. 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.

    lines 92–95

    uses SimpleGraph.isTree_iff_connected_and_card, Op1239Tree36.graph_connected, Nat.card_eq_fintype_card, SimpleGraph.edgeFinset_card, Op1239Tree36.graph_edges

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

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