op223_example_graph_is_tree
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
- op223_example_graphThe eight-vertex tree with edges 01, 04, 07, 12, 23, 45 and 46.
- Arena.Reachable.transReachability is transitive.
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.
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.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical 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 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.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical 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]
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|.
uses
SimpleGraph.isTree_iff_connected_and_card.mprapply SimpleGraph.isTree_iff_connected_and_card.mpr constructor
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.
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
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.
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).
- The preparatory lemma op223_example_edges verifies edge set membership by an exhaustive check over all 64 pairs in Fin 8 × Fin 8 via classical simplification.
- The final cardinality condition |E| + 1 = |V| (evaluated as 7 + 1 = 8) is resolved automatically by norm_num by computing the size of the 7-element edge finset and the 8-element vertex type Fin 8.
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.
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]