op223_weighted_eleven_graph_is_tree
The support graph of the eleven-vertex rational weighted-shift candidate is a tree.
Statement
theorem op223_weighted_eleven_graph_is_tree : op223_weighted_eleven_graph.IsTree- Source
- The finite rational weighted-shift candidate.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- op223_weighted_eleven_graphThe eleven-vertex support tree of the rational weighted-shift candidate.
- Arena.Reachable.transReachability is transitive.
The proof, explained
The proof establishes that the 11-vertex support graph is a tree by showing it is connected and has 10 edges, satisfying the characterization |E| + 1 = |V|. Connectedness is proven by showing vertex 0 can reach every other vertex along explicit paths, and the edge count is computed directly from the explicit set of 10 generating edges.
The edge set of op223_weighted_eleven_graph is precisely the 10-element set of candidate edges.
By definition, SimpleGraph.fromEdgeSet creates a graph whose edges are the given pairs without self-loops. Because none of the 10 edges are loops (verified by decide), the diagonal set has empty intersection with the edges, so the edge set is exactly the given 10 edges.
uses
op223_weighted_eleven_graph,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_eleven_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(0,10)} : Finset (Sym2 (Fin 11))), ¬ x.IsDiag := by decide apply h e simpa only [Finset.mem_insert, Finset.mem_singleton] using he
The 10 candidate edges are each adjacent in the graph.
Each of the 10 pairs (0,1), (1,2), (2,3), (3,4), (4,5), (0,6), (0,7), (7,8), (8,9), and (0,10) is verified to be an edge of op223_weighted_eleven_graph by unfolding the graph definition and simplifying using the adjacency rule for graphs from edge sets and pair symmetry.
uses
op223_weighted_eleven_graph,SimpleGraph.fromEdgeSet_adj,Sym2.eqclassical have e01 : op223_weighted_eleven_graph.Adj 0 1 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e12 : op223_weighted_eleven_graph.Adj 1 2 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e23 : op223_weighted_eleven_graph.Adj 2 3 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e34 : op223_weighted_eleven_graph.Adj 3 4 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e45 : op223_weighted_eleven_graph.Adj 4 5 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e06 : op223_weighted_eleven_graph.Adj 0 6 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e07 : op223_weighted_eleven_graph.Adj 0 7 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e78 : op223_weighted_eleven_graph.Adj 7 8 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e89 : op223_weighted_eleven_graph.Adj 8 9 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e010 : op223_weighted_eleven_graph.Adj 0 10 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq]
To show the graph is a tree, it suffices to show it is connected and has |E| + 1 = |V|.
We apply SimpleGraph.isTree_iff_connected_and_card.mpr, which states that a finite graph with |E| + 1 = |V| is a tree if and only if it is connected, and split the goal into connectedness and the cardinality equality.
uses
SimpleGraph.isTree_iff_connected_and_card.mprapply SimpleGraph.isTree_iff_connected_and_card.mpr constructor
Connectedness reduces to showing every vertex is reachable from vertex 0.
A graph is connected if some vertex can reach all vertices. We choose vertex 0 as this root and consider an arbitrary vertex x.
uses
SimpleGraph.connected_iff_exists_forall_reachable· rw [SimpleGraph.connected_iff_exists_forall_reachable] refine ⟨0, ?_⟩ intro x
Vertex 0 can reach every vertex in Fin 11.
By case exhaustion on x in Fin 11, vertex 0 reaches 0 reflexively; vertices 1, 6, 7, 10 directly via an edge; vertices 2, 3, 4, 5 along the path 0-1-2-3-4-5; and vertices 8, 9 along the path 0-7-8-9, chaining reachability transitively.
uses
Reachable.rflfin_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 e010.reachableThe number of edges plus one equals the number of vertices, 10 + 1 = 11.
Rewriting the edge set with op223_weighted_eleven_edges and converting to finite set cardinalities, norm_num evaluates the size of the 10-element edge set and the 11-element vertex set, verifying 10 + 1 = 11.
uses
Nat.card_coe_set_eq,op223_weighted_eleven_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_eleven_edges, Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]
op223_weighted_eleven_graph- The graph op223_weighted_eleven_graph is defined from the specified set of 10 unordered pairs of vertices in Fin 11.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of a graph constructed from an edge set s consists of all edges in s except self-loops (the diagonal).
Set.mem_sdiff- Membership in a set difference s \\ t means belonging to s and not belonging to t.
Sym2.mem_diagSet- Membership in Sym2.diagSet is equivalent to being a diagonal pair (a loop).
Set.mem_insert_iff- Membership in insert a s is equivalent to being equal to a or belonging to s.
Set.mem_singleton_iff- Membership in the singleton set {b} is equivalent to equality with b.
Finset.mem_coe- Coercion from Finset to Set preserves membership.
Finset.mem_insert- Membership in insert b s for a finset is equivalent to equality with b or membership in s.
Finset.mem_singleton- Membership in a singleton finset {a} is equivalent to equality with a.
And.left- From a conjunction a ∧ b, the left conjunct a holds.
SimpleGraph.fromEdgeSet_adj- Vertices v and w are adjacent in SimpleGraph.fromEdgeSet s iff the pair s(v, w) is in s and v ≠ w.
Sym2.eq- Unordered pairs s(a, b) and s(c, d) are equal iff (a = c ∧ b = d) or (a = d ∧ b = c).
SimpleGraph.isTree_iff_connected_and_card.mpr- A graph on a finite type is a tree if and only if it is connected and |E| + 1 = |V|.
SimpleGraph.connected_iff_exists_forall_reachable- A graph is connected if and only if there is a vertex that can reach every vertex.
Reachable.rfl- Every vertex is reachable from itself.
Nat.card_coe_set_eq- The cardinality of a coerced set equals its ncard.
op223_weighted_eleven_edges- The edge set of op223_weighted_eleven_graph is exactly the set of the 10 specified edges.
Set.ncard_coe_finset- The ncard of a coerced finset equals the finset cardinality.
Finset.card_insert_eq_ite- The cardinality of insert a s is s.card if a ∈ s, and s.card + 1 otherwise.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Nat.card_eq_fintype_card- For a finite type α, Nat.card α equals Fintype.card α.
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_eleven_edges : op223_weighted_eleven_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(0,10)} : Finset (Sym2 (Fin 11))) : Set (Sym2 (Fin 11))) := by classical rw [op223_weighted_eleven_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(0,10)} : Finset (Sym2 (Fin 11))), ¬ x.IsDiag := by decide apply h e simpa only [Finset.mem_insert, Finset.mem_singleton] using hetheorem op223_weighted_eleven_graph_is_tree : op223_weighted_eleven_graph.IsTree := by classical have e01 : op223_weighted_eleven_graph.Adj 0 1 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e12 : op223_weighted_eleven_graph.Adj 1 2 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e23 : op223_weighted_eleven_graph.Adj 2 3 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e34 : op223_weighted_eleven_graph.Adj 3 4 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e45 : op223_weighted_eleven_graph.Adj 4 5 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e06 : op223_weighted_eleven_graph.Adj 0 6 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e07 : op223_weighted_eleven_graph.Adj 0 7 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e78 : op223_weighted_eleven_graph.Adj 7 8 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e89 : op223_weighted_eleven_graph.Adj 8 9 := by simp [op223_weighted_eleven_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have e010 : op223_weighted_eleven_graph.Adj 0 10 := by simp [op223_weighted_eleven_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 e010.reachable · rw [Nat.card_coe_set_eq, op223_weighted_eleven_edges, Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Sym2.eq, Fin.ext_iff, Nat.card_eq_fintype_card]