op223_weighted_support_graph_is_tree
The support graph of the rational weighted-shift candidate is a tree.
Statement
theorem op223_weighted_support_graph_is_tree : op223_weighted_support_graph.IsTree- Source
- The finite weighted-shift counterexample candidate.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- op223_weighted_support_graphThe thirteen-vertex tree obtained by deleting the pendant edge from the rational weighted-shift candidate.
- Arena.Reachable.transReachability is transitive.
The proof, explained
The theorem proves that the support graph on 13 vertices is a tree using the characterization that a finite simple 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 established by showing that every vertex is reachable from vertex 0 along paths formed by the graph's 12 defined edges. A helper lemma identifies the edge set with the explicit 12-element set by checking that no edge is a self-loop. Finally, arithmetic computation verifies that the 12 edges and 13 vertices satisfy |E| + 1 = |V|.
The edge set of the support graph consists exactly of the 12 specified vertex pairs.
By definition, a simple graph constructed from a set of pairs has as its edges all pairs in that set that are not self-loops (diagonal elements). Since an exhaustive check via decision procedure shows that none of the 12 specified pairs are diagonal, the edge set coincides with the 12-element set.
uses
SimpleGraph.edgeSet_fromEdgeSet,Set.mem_sdiff,Sym2.mem_diagSet,Set.mem_insert_iff,Set.mem_singleton_iff,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,And.leftclassical rw [op223_weighted_support_graph, SimpleGraph.edgeSet_fromEdgeSet] ext e simp only [Set.mem_sdiff, Sym2.mem_diagSet, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] constructor · exact And.left · intro he refine ⟨he, ?_⟩ have h : ∀ x ∈ ({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))), ¬ x.IsDiag := by decide apply h e simpa only [Finset.mem_insert, Finset.mem_singleton] using he
Each of the 12 specified vertex pairs forms an edge in the support graph.
For each pair (0,1), (1,2), (2,3), (3,4), (4,5), (0,6), (0,7), (7,8), (8,9), (9,10), (10,11), and (11,12), adjacency holds by simplifying against the graph's definition and the condition that the two endpoints are distinct.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical have e01 : op223_weighted_support_graph.Adj 0 1 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e12 : op223_weighted_support_graph.Adj 1 2 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e23 : op223_weighted_support_graph.Adj 2 3 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e34 : op223_weighted_support_graph.Adj 3 4 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e45 : op223_weighted_support_graph.Adj 4 5 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e06 : op223_weighted_support_graph.Adj 0 6 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e07 : op223_weighted_support_graph.Adj 0 7 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e78 : op223_weighted_support_graph.Adj 7 8 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e89 : op223_weighted_support_graph.Adj 8 9 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e910 : op223_weighted_support_graph.Adj 9 10 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e1011 : op223_weighted_support_graph.Adj 10 11 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e1112 : op223_weighted_support_graph.Adj 11 12 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
To prove that the graph is a tree, it suffices to show that it is connected and that |E| + 1 = |V|.
By the standard characterization of finite trees, a simple graph is a tree if and only if it is connected and its number of edges plus one equals its number of vertices. Applying this characterization splits the goal into two subgoals: connectedness and the cardinality equality.
uses
SimpleGraph.isTree_iff_connected_and_card.mprapply SimpleGraph.isTree_iff_connected_and_card.mpr constructor
The support graph is connected because every vertex is reachable from vertex 0.
A graph is connected if and only if there is a vertex from which all vertices are reachable. Choosing 0 as the root, an exhaustive case analysis on all 13 vertices of Fin 13 establishes reachability: 0 is reachable from itself by reflexivity; 1 through 5 are reachable along the path 0–1–2–3–4–5; 6 is an immediate neighbor of 0; and 7 through 12 are reachable along the path 0–7–8–9–10–11–12.
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 ((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable · exact (((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable).trans e45.reachable · exact e06.reachable · exact e07.reachable · exact e07.reachable.trans e78.reachable · exact (e07.reachable.trans e78.reachable).trans e89.reachable · exact ((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable · exact (((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable · exact ((((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable).trans e1112.reachable
The number of edges plus one equals the number of vertices (12 + 1 = 13), completing the proof that the graph is a tree. automation
Rewriting with the helper lemma op223_weighted_support_edges converts the edge set cardinality into the size of the explicit 12-element set. Normalization and computation confirm that the edge set has cardinality 12 and Fin 13 has cardinality 13, satisfying 12 + 1 = 13.
uses
Nat.card_coe_set_eq,op223_weighted_support_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_weighted_support_edges, Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
And.left- From a conjunction a ∧ b, one deduces the left conjunct a.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_insert_eq_ite- Inserting an element into a finite set increases its cardinality by 1 if the element was not already present, and leaves it unchanged otherwise.
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton finite set {a} if and only if it equals a.
Nat.card_eq_fintype_card- The cardinal number of a finite type equals the cardinality given by its Fintype instance.
Nat.card_coe_set_eq- The cardinal number of a coerced set equals its finite cardinality (ncard).
op223_weighted_support_edges- The edge set of the candidate support graph consists precisely of the 12 specified unordered pairs.
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 finite set cardinality (card).
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
SimpleGraph.connected_iff_exists_forall_reachable- A graph is connected if and only if there exists a vertex that can reach every vertex.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of a simple graph generated from a set of pairs s is s minus all diagonal pairs (self-loops).
SimpleGraph.fromEdgeSet_adj- Two vertices v and w are adjacent in SimpleGraph.fromEdgeSet s if and only if the pair s(v, w) is in s and v ≠ w.
SimpleGraph.isTree_iff_connected_and_card.mpr- A simple graph on a finite vertex set is a tree if and only if it is connected and |E| + 1 = |V|.
Sym2.eq- Two unordered pairs s(a, b) and s(c, d) are equal if and only if (a = c ∧ b = d) or (a = d ∧ b = c).
Sym2.mem_diagSet- An unordered pair belongs to the diagonal set if and only if both endpoints are equal.
- The verification that none of the 12 candidate edges are self-loops and the cardinality computation for the edge set are discharged by Lean's computational automation (`decide` and `norm_num`).
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 1000000set_option maxRecDepth 10000lemma op223_weighted_support_edges : op223_weighted_support_graph.edgeSet = (({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))) : Set (Sym2 (Fin 13))) := by classical rw [op223_weighted_support_graph, SimpleGraph.edgeSet_fromEdgeSet] ext e simp only [Set.mem_sdiff, Sym2.mem_diagSet, Set.mem_insert_iff, Set.mem_singleton_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] constructor · exact And.left · intro he refine ⟨he, ?_⟩ have h : ∀ x ∈ ({s(0,1), s(1,2), s(2,3), s(3,4), s(4,5), s(0,6), s(0,7), s(7,8), s(8,9), s(9,10), s(10,11), s(11,12)} : Finset (Sym2 (Fin 13))), ¬ x.IsDiag := by decide apply h e simpa only [Finset.mem_insert, Finset.mem_singleton] using hetheorem op223_weighted_support_graph_is_tree : op223_weighted_support_graph.IsTree := by classical have e01 : op223_weighted_support_graph.Adj 0 1 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e12 : op223_weighted_support_graph.Adj 1 2 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e23 : op223_weighted_support_graph.Adj 2 3 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e34 : op223_weighted_support_graph.Adj 3 4 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e45 : op223_weighted_support_graph.Adj 4 5 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e06 : op223_weighted_support_graph.Adj 0 6 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e07 : op223_weighted_support_graph.Adj 0 7 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e78 : op223_weighted_support_graph.Adj 7 8 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e89 : op223_weighted_support_graph.Adj 8 9 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e910 : op223_weighted_support_graph.Adj 9 10 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e1011 : op223_weighted_support_graph.Adj 10 11 := by simp [op223_weighted_support_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e1112 : op223_weighted_support_graph.Adj 11 12 := by simp [op223_weighted_support_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 ((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable · exact (((e01.reachable.trans e12.reachable).trans e23.reachable).trans e34.reachable).trans e45.reachable · exact e06.reachable · exact e07.reachable · exact e07.reachable.trans e78.reachable · exact (e07.reachable.trans e78.reachable).trans e89.reachable · exact ((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable · exact (((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable · exact ((((e07.reachable.trans e78.reachable).trans e89.reachable).trans e910.reachable).trans e1011.reachable).trans e1112.reachable · rw [Nat.card_coe_set_eq, op223_weighted_support_edges, Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]