AFTD Auto-Formalizing Theoretical Domains

op223_example_graph_is_tree

theoremverified

The eight-vertex example graph op223_example_graph is a tree.

Statement

theorem op223_example_graph_is_tree : op223_example_graph.IsTree
Source
step towards op223_example_graph_sustainable
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

To prove that the eight-vertex graph op223_example_graph is a tree, the proof applies the standard characterization that a finite graph is a tree if and only if it is connected and |E| + 1 = |V|. Connectivity is established by choosing vertex 0 as a root and constructing paths to every other vertex using the transitivity of reachability along the known edges. The edge count is computed using a preparatory lemma that identifies the edge set as an explicit finset of size 7, after which numerical computation confirms 7 + 1 = 8.

  1. The edge set of op223_example_graph consists precisely of the seven specified unordered pairs: s(0,1), s(0,4), s(0,7), s(1,2), s(2,3), s(4,5), and s(4,6). automation

    By extensionality on unordered pairs of vertices (e = s(a, b) via Sym2.ind), we exhaust all 64 possible pairs (a, b) in Fin 8 × Fin 8 using fin_cases. For every pair, simplification expands the definition of op223_example_graph, the condition for edge set membership, and equality of pairs in Sym2, confirming that the graph's edges match the given set.

    lines 7–12

    uses Sym2.ind, SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj, Sym2.eq

      classical
      ext e
      induction e using Sym2.ind with
      | _ a b =>
        fin_cases a <;> fin_cases b <;>
          simp [op223_example_graph, SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
  2. The seven pairs (0,1), (0,4), (0,7), (1,2), (2,3), (4,5), and (4,6) are adjacent in op223_example_graph. automation

    For each of the seven edges, adjacency is verified directly by simplifying with the definition of the graph from its edge set and the equality condition for unordered pairs.

    lines 16–23

    uses SimpleGraph.fromEdgeSet_adj, Sym2.eq

      classical
      have e01 : op223_example_graph.Adj 0 1 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e04 : op223_example_graph.Adj 0 4 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e07 : op223_example_graph.Adj 0 7 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e12 : op223_example_graph.Adj 1 2 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e23 : op223_example_graph.Adj 2 3 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e45 : op223_example_graph.Adj 4 5 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
      have e46 : op223_example_graph.Adj 4 6 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
  3. To show op223_example_graph is a tree, it suffices to prove that it is connected and that the number of edges plus one equals the number of vertices.

    We apply the characterization of finite trees (SimpleGraph.isTree_iff_connected_and_card.mpr), which reduces the goal to two independent obligations: connectivity of the graph and the cardinality equation |E| + 1 = |V|.

    lines 24–25

    uses SimpleGraph.isTree_iff_connected_and_card.mpr

      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
  4. op223_example_graph is connected.

    A graph is connected if and only if some vertex can reach every other vertex (SimpleGraph.connected_iff_exists_forall_reachable). Choosing vertex 0 as the root, we check each of the eight vertices x in Fin 8 by case exhaustion: 0 reaches itself by reflexivity (Reachable.rfl); vertices 1, 4, and 7 are reached directly along edges e01, e04, and e07; and vertices 2, 3, 5, and 6 are reached by chaining adjacent edges together via the transitivity of reachability.

    lines 26–36

    uses SimpleGraph.connected_iff_exists_forall_reachable, Reachable.rfl

      · rw [SimpleGraph.connected_iff_exists_forall_reachable]
        refine ⟨0, ?_⟩
        intro x; fin_cases x
        · exact Reachable.rfl
        · exact e01.reachable
        · exact e01.reachable.trans e12.reachable
        · exact (e01.reachable.trans e12.reachable).trans e23.reachable
        · exact e04.reachable
        · exact e04.reachable.trans e45.reachable
        · exact e04.reachable.trans e46.reachable
        · exact e07.reachable
  5. The number of edges in op223_example_graph plus one equals the number of vertices, completing the proof. automation

    We rewrite the cardinality of the edge set in terms of finite set cardinality using Nat.card_coe_set_eq, replace the edge set with the explicit seven-element finset via the lemma op223_example_edges, and apply Set.ncard_coe_finset. An automated evaluation using norm_num expands the size of the 7-element set and verifies that 7 + 1 = 8.

    lines 37–38

    uses Nat.card_coe_set_eq, op223_example_edges, Set.ncard_coe_finset, Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card

      · rw [Nat.card_coe_set_eq, op223_example_edges, Set.ncard_coe_finset]
        norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Finset.card_insert_eq_ite
The cardinality of inserting an element a into a finite set s is s.card if a is already in s, and s.card + 1 otherwise.
Nat.card_eq_fintype_card
The cardinality Nat.card of a finite type equals its Fintype cardinality.
Nat.card_coe_set_eq
The cardinality Nat.card of a set coerced to a type equals its set cardinality ncard.
op223_example_edges
The edge set of op223_example_graph is equal to the set of seven unordered pairs s(0,1), s(0,4), s(0,7), s(1,2), s(2,3), s(4,5), and s(4,6).
Reachable.rfl
Every vertex in a graph is reachable from itself.
Set.ncard_coe_finset
The set cardinality ncard of a coerced finite set equals its finset cardinality card.
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.fromEdgeSet_adj
In the graph constructed from an edge set s, vertices v and w are adjacent if and only if s(v, w) ∈ s and v ≠ w.
SimpleGraph.isTree_iff_connected_and_card.mpr
A graph is a tree if it is connected and its number of edges plus one equals its number of vertices.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
Sym2.eq
Two unordered pairs s(a, b) and s(c, d) are equal if and only if (a = c and b = d) or (a = d and b = c).
Sym2.ind
To prove a proposition for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).

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

open SimpleGraphopen scoped Classicalset_option maxHeartbeats 1000000 inlemma op223_example_edges : op223_example_graph.edgeSet =    (({s(0,1), s(0,4), s(0,7), s(1,2), s(2,3), s(4,5), s(4,6)} : Finset (Sym2 (Fin 8))) : Set (Sym2 (Fin 8))) := by  classical  ext e  induction e using Sym2.ind with  | _ a b =>    fin_cases a <;> fin_cases b <;>      simp [op223_example_graph, SimpleGraph.mem_edgeSet, SimpleGraph.fromEdgeSet_adj, Sym2.eq]/-- The eight-vertex example graph op223_example_graph is a tree. -/theorem op223_example_graph_is_tree : op223_example_graph.IsTree := by  classical  have e01 : op223_example_graph.Adj 0 1 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e04 : op223_example_graph.Adj 0 4 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e07 : op223_example_graph.Adj 0 7 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e12 : op223_example_graph.Adj 1 2 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e23 : op223_example_graph.Adj 2 3 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e45 : op223_example_graph.Adj 4 5 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  have e46 : op223_example_graph.Adj 4 6 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]  apply SimpleGraph.isTree_iff_connected_and_card.mpr  constructor  · rw [SimpleGraph.connected_iff_exists_forall_reachable]    refine ⟨0, ?_⟩    intro x; fin_cases x    · exact Reachable.rfl    · exact e01.reachable    · exact e01.reachable.trans e12.reachable    · exact (e01.reachable.trans e12.reachable).trans e23.reachable    · exact e04.reachable    · exact e04.reachable.trans e45.reachable    · exact e04.reachable.trans e46.reachable    · exact e07.reachable  · rw [Nat.card_coe_set_eq, op223_example_edges, Set.ncard_coe_finset]    norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
See it in the graphDiscuss this resultChallenge it